Архив Зеленоградского турнира

Мы обнаружили самый быстрый способ передачи информации заявили ученые Байтсити и назвали его блингорс. Блингорс несравнимо лучше чем любой другой известный способ передачи информации. Многие компании в Байтлэнд начали строить сети основанные на блингорс, развивая таким образом информационную инфраструктуру королевства Байтлэнд. Главная задача это построить ядро сети, соединяющей основные города страны. Стоимость построения блингорс между двумя городами зависит от множества факторов, но она была точно подсчитана. Ваша задача разработать топологию сети таким образом, что бы любые два города королевства были связаны и стоимость строительства сети была бы минимальна.

Замечания

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

s [число тестовых последовательностей <= 10]
n [число городов <= 10 000]
NAME [имя города]
p [число городов соседствующих с данным NAME]
neigh cost 
     [neigh - номер города из общего списка городов
      cost - стоиость постройки блнгорс из данного города NAME до neigh]
[пустая строчка между тестами]

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

[на отдельных строчках] cost [минимальная стоимость постройки сети]

Пример

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

2

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

3
shodnya
2
2 1
3 3
malino
2
1 1
3 7
klin
2
1 3 
2 7


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

3
4