Безпечний шлях
Крілик Пітер роздобув карту міста з позначеними на ній барами. Пітер любить відвідувати бари. Зрозуміло, що відвідувати бари потрібно вночі, щоб було вдвічі цікавіше. Пітерові може надоїсти сидіти в одному барі, тому він частенько заходить у декілька барів за один вечір.
Сьогодні Пітер вирішив відвідати два заклади. Між деякими барами є дороги. У темних провулках може бути небезпечно, тому Пітер оцінив кожну дорогу між барами величиною небезпеки: чим вона більша, тим небезпечніший шлях. Прямої дороги від одного бару до іншого може й не бути, але між кожною парою барів існує шлях, що проходить, можливо, через декілька інших барів. У цьому випадку небезпека всього шляху дорівнює найбільшій небезпеці доріг на шляху.
Пітер склав список можливих пар барів, які він збирається відвідати. Для кожної пари йому потрібно знати найбезпечніший шлях між ними. Допомогти Пітерові у цьому – Ваше завдання.
Вхідні дані
Перший рядок містить три цілих числа, відокремлені пропусками: n m q (1 ≤ n ≤ 100000, 1 ≤ m, q ≤ 200000) – відповідно, кількість барів, кількість доріг між барами і кількість можливих пар для відвідування. Далі m рядків описують дороги, кожен містить три числа, відокремлені пропусками: a b c (0 ≤ a, b < n, 1 ≤ c ≤ 10000) – відповідно, бари, з’єднані дорогою, та її небезпека. Останні q рядків описують пари барів, які, можливо, відвідає Пітер – кожен містить два числа через пропуск: a b (0 ≤ a, b < n).
Вихідні дані
Для кожної пари зі списку Пітера виведіть в окремому рядку відповідь – небезпеку найбезпечнішого шляху між барами.