Alternatywne formaty: PostScript | PDF

Ministerstwo Infrastruktury Bajtocji postanowiło stworzyć program pozwalający szybko obliczać długości tras między dowolnymi miastami. Nie byłoby w tym nic dziwnego, gdyby nie fakt, iż mieszkańcy Bajtocji nie zawsze szukają najkrótszej trasy. Zdarza się, że pragną dowiedzieć się o k-tą co do długości najkrótszą trasę. Dopuszczamy zapętlenia tras, tzn. takie trasy, na których miasta powtarzają się.

Przykład

Jeśli między dwoma miastami istnieją 4 trasy o długościach: 2, 4, 4 i 5, to najkrótsze połączenie ma długość 2, drugie co do długości 4, trzecie 4, a czwarte 5.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis sieci dróg Bajtocji oraz zapytania dotyczące długości tras przejazdu,
• obliczy i wypisze na standardowe wyjście odpowiedzi do wczytanych zapytań.

Wejście

W pierwszym wierszu standardowego wejścia zapisane są dwie dodatnie liczby całkowite n i m oddzielone pojedynczym odstępem, 1 <= n <= 100, 0 <= m <= n²-n. Są to odpowiednio liczba miast w Bajtocji oraz liczba dróg łączących miasta. Miasta są ponumerowane od 1 do n.

W każdym z kolejnych m wierszy znajdują się po trzy liczby całkowite oddzielone pojedynczymi odstępami: a, b i d, a <> b, 1 <= d <= 500. Każda taka trójka opisuje jedną, jednokierunkową drogę długości d umożliwiającą przejechanie z miasta a do b. Dla każdych dwóch miast istnieje co najwyżej jedna droga umożliwiająca przejazd w danym kierunku.

W kolejnym wierszu znajduje się jedna liczba całkowita q, 1 <= q <= 10000, oznaczająca ilość zapytań. W kolejnych q wierszach są zapisane zapytania, po jednym w wierszu. Każde zapytanie to trzy liczby całkowite oddzielone pojedynczymi odstępami: c, d i k, 1 <= k <= 100. Zapytanie takie dotyczy długości k-tej najkrótszej trasy z miasta c do miasta d.

Wyjście

Twój program powinien wypisywać odpowiedzi na wczytane zapytania na standardowe wyjście, po jednej odpowiedzi w wierszu. W i-tym wierszu powinna zostać wypisana odpowiedź na i-te zapytanie - jedna liczba całkowita równa szukanej długości trasy lub -1, gdy taka trasa nie istnieje.

Przykład

Dla danych wejściowych:

5 5
1 2 3
2 3 2
3 2 1
1 3 10
1 4 1
8
1 3 1
1 3 2
1 3 3
1 4 2
2 5 1
2 2 1
2 2 2
1 1 2

poprawnym wynikiem jest:

5
8
10
-1
-1
3
6
-1