Najkrótsza ścieżka (The Shortest Path)

Dana jest lista miast. Każde bezpośrednie połączenie pomiędzy dwoma miastami ma stoważyszony z nim koszt (liczba całkowita większa niż 0). Celem jest nalezienie ścieżek o minimalnym koszcie pomiędzy parami miast. Zakładamy, że koszt każdej ścieżki (liczony jako suma kosztów wszystkich bezpośrednich połączeń należących do ścieżki) wynosi co najwyżej 200000. Nazwa każdego miasta to napis złożony ze znaków a,...,z o długości co najwyżej 10.

Wejście

s [liczba przypadków testowych <= 10]
n [liczba miast <= 10000]
NAME [nazwa miasta]
p [liczba miast sąsiednich do miasta NAME]
nr cost [nr - numer miasta połączonego z miastem NAME (indeks pierwszego miasta to 1)]
           [cost - koszt połączenia]
r [liczba ścieżek do znalezienia <= 100]
NAME1 NAME2 [NAME1 - nazwa miasta startowego, NAME2 - nazwa miasta docelowego]
[pusta linia odziela przypadki testowe]

Wyjście

cost [koszt optymalnego (o najniższym koszcie) połączenia pomiędzy miastami NAME1 i NAME2 (w osobnych liniach)]

Przykład

Wejście:
1
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
2
gdansk warszawa
bydgoszcz warszawa

Wyjście:
3
2