Є \(n\) міст і \(m\) доріг між ними. Ваше завдання — обробити \(q\) запитів, де вам потрібно визначити довжину найкоротшого маршруту між двома заданими містами.

Обмеження

• \(1≤n≤500\)
• \(1≤m≤n^2\)
• \(1≤q≤10^5\)
• \(1≤a,b≤n\)
• \(1≤c≤10^9\)

Формат вхідних даних

У першому рядку є три цілі числа \(n\), \(m\) і \(q\): кількість міст, доріг і запитів.

Потім є \(m\) рядків, що описують дороги. У кожному рядку є три цілі числа \(a, b, c\): між містами \(a\) і \(b\) є дорога довжиною \(c\). Усі дороги є двосторонніми.

Нарешті, є \(q\) рядків, що описують запити. У кожному рядку два цілі числа \(a\) і \(b\): визначити довжину найкоротшого маршруту між містами \(a\) і \(b\).

Формат вихідних даних

Виведіть довжину найкоротшого маршруту для кожного запиту. Якщо маршруту немає, виведіть −1.

Приклад вхідних даних

4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2

Приклад вихідних даних

5
5
8
-1
3