01. Кратчайший путь

Дан набор городов. Каждая дорога соединяющая города имеет стоимость передвижения (целое число больше 0). НЕобходимо найти путь наименьшей стоимости между любыми двумя городами. Стоимость любого пути (которая равна сумме стоимостей всех дорог состовляющих путь) не превышает 200000. Имена городов это строки содержащие символы 'a'...'z' и не превышающие по длине 10.

Входные данные

s [число тестов <= 10]
n [число городов <= 10000]
NAME [имя города]
p [число соседних городов NAME]
nr cost [nr - индекс города соединенного с NAME (индекс первого города - 1)]
           [cost - стоимость передвижения]
r [число путей которые необходимо найти<= 100]
NAME1 NAME2 [NAME1 - начало пути, NAME2 - место назначения]
[пустая строчка разделяющая тесты]

Выходные данные

cost [минимальная стоимость проезда из города NAME1 до города NAME2 (по одной на каждой строчке)]

Пример

Входные данные:

1
4
zelenograd
2
2 1
3 3
himki
3
1 1
3 1
4 4
piter
3
1 3
2 1
4 1
moscow
2
2 4
3 1
2
zelenograd moscow
himki moscow

Выходные данные:

3
2