Połączenia
Limit pamięci: 32 MB
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 -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 i
oddzielone pojedynczym odstępem,
, .
Są to odpowiednio liczba miast w Bajtocji oraz
liczba dróg łączących miasta.
Miasta są ponumerowane od do .
W każdym z kolejnych wierszy znajdują się po trzy liczby całkowite
oddzielone pojedynczymi odstępami: , i ,
, .
Każda taka trójka opisuje jedną, jednokierunkową drogę długości
umożliwiającą przejechanie z miasta do .
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 ,
, oznaczająca ilość zapytań.
W kolejnych wierszach są zapisane zapytania, po jednym w wierszu.
Każde zapytanie to trzy liczby całkowite
oddzielone pojedynczymi odstępami: , i ,
.
Zapytanie takie dotyczy długości -tej najkrótszej trasy
z miasta do miasta .
Wyjście
Twój program powinien wypisywać odpowiedzi na wczytane zapytania
na standardowe wyjście, po jednej odpowiedzi w wierszu.
W -tym wierszu powinna zostać wypisana
odpowiedź na -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
poprawną odpowiedzią jest:
5
8
10
-1
-1
3
6
-1
Autor zadania: Krzysztof Sikora.