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