Problem description

Januszex S.A. pod wodzą prezesa Pana Janusza dzielnie się rozwija. Firma stawia teraz na własną sprzedaż wysyłkową, rozwój sieci dystrybucyjnej i budowę magazynów. Pan Janusz załatwił już flotę ciężarówek do przewozu paczek, jednak na horyzoncie już pojawia się problem: ograniczenia tonażu na drogach krajowych.

W kraju jest wiele miast połączonych dwukierunkowymi drogami. Na każdej drodze obowiązuje ustalone i znane ograniczenie tonażu. Pan Janusz zauważył, że w firmie przydałby się system planujący trasy, który obliczałby dla wielu zapytań o przewóz towaru pomiędzy pewnymi dwoma miastami, jak ciężką ciężarówkę może posłać w trasę, aby nie naruszyć żadnego ograniczenia tonażu. Przygotowanie takiego systemu informatycznego oczywiście przypadło w udziale Tobie.

Napisz program, który: wczyta sieć połączeń w kraju oraz zapytania do systemu, dla każdego zapytania wyznaczy jak ciężką ciężarówkę można posłać w trasę i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, oddzielone pojedynczym odstępem i określające kolejno: liczbę miast oraz dróg między nimi. W kolejnych M wierszach znajduje się opis dróg. Opis każdej drogi składa się z trzech liczb całkowitych u_i, v_i oraz c_i, pooddzielanych pojedynczymi odstępami – określających istnienie drogi pomiędzy miastami o numerach u_i oraz v_i o ograniczeniu tonażu do c_i ton.

W kolejnym wierszu znajduje się jedna liczba naturalna Q, określająca liczbę zapytań do programu. W kolejnych Q wierszach znajdują się kolejne zapytania. Opis każdego zapytania składa się z dwóch liczb naturalnych a_i oraz b_i, oddzielonych pojedynczym odstępem – określających transport pomiędzy miastami o numerach a_i oraz b_i (a_i ≠ b_i).

Miasta numerowane są kolejnymi liczbami naturalnymi od 1 do N włącznie. Sieć połączeń jest spójna – między każdą parą miast istnieje (niekoniecznie bezpośrednie) połączenie z użyciem dróg krajowych. Dodatkowo, między każdą parą miast istnieje co najwyżej jedna bezpośrednia droga.

Wyjście

Twój program powinien wypisać na wyjście Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zapytania – maksymalna masa ciężarówki, która może wyruszyć w trasę bez naruszenia ograniczenia tonażu.

Ograniczenia

1 ≤ N ≤ 200 000, 0 ≤ M ≤ 500 000, 1 ≤ Q ≤ 200 000, 1 ≤ c_i ≤ 10⁹.

Przykład

6 7
1 2 5
2 3 2
3 1 4
3 4 3
4 5 7
5 6 1
4 6 6
3
1 6
5 6
3 4

3
6
3