AlgoLiga 2018

Profesor Algobit zmęczony rokiem akademickim i wymyślaniem zadań na kolejne terminy egzaminu ze "Wstępu do algorytmów" wybiera się na wakacje w góry. Ma zamiar spędzić czas wędrując. Właśnie ogląda mapę, na której zaznaczono n szczytów połączonych za pomocą m dwukierunkowych szlaków. Jest już wrzesień i pogoda bywa zmienna zatem wędrując po górach należy zachować ostrożność dlatego profesor chciałby uniknąć wędrowania na zbyt dużej wysokości. Szczęśliwie, dla każdego szlaku na mapie zaznaczone jest, ile metrów nad poziomem morza znajuje się najwyższy punkt z danego szlaku.

Profesor planuje teraz q wędrówek między szczytami gór. Dla każdej z tych wędrówek chciałby poznać minimalną liczbę M, taką że cała trasa wędrówki będzie prowadzić nie wyżej niż M metrów nad poziomem morza.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne: 2<=n<=5000, 1<=m<=500000, 1<=q<=10000, oznaczające kolejno liczbę szczytów górskich, liczbę łączących je szlaków oraz liczbę wędrówek które planuje profesor. Szczyty górskie są ponumerowane od 1 do n.

W każdym z następnych m wierszy znajduje się opis jednego szlaku w postaci kolejno trzech liczb całkowitych: a, b, c (1<=a!=b<=n, 1<=c<=100000, znak "!=" to znak różności). Oznacza to, że szczyty o numerach a i b są połączone szlakiem którego najwyższy punkt znajduje się c metrów nad poziomem morza. Każde dwa szczyty są połączone co najwyżej jednym szlakiem oraz pomiędzy dowolną parą szczytów można przejść korzystając ze szlaków.

Następne q wieszy opisuje wędrówki planowane przez profesora. W i-tym z tych wierszy znajdują się dwie liczby całkowite: 1<=x!=y<=n. Oznaczają one, że w trakcie i-tej wędrówki profesor chciałby przejść ze szczytu o numerze x do szczytu o numerze y.

Wyjście

Na wyjście należy wypisać q wierszy, po jednym dla każdej planowanej wędrówki. W i-tym z tych wierszy powinna znaleźć się liczba M - najmniejsza liczba całkowita taka, że między szczytami z i-tej wędrówki można przejść nie wchodząc nigdy na wysokość większą niż M metrów nad poziomem morza

Przykład

Wejście:
5 7 4
2 5 10
5 1 2
1 2 1
5 3 200
4 1 3
2 4 3
1 3 100
3 5
5 4
2 1
2 4

Wyjście:
100
3
1
3