Одному очень хорошему человеку требуется написать задание для зачета, которое проверит автоматическая проверяющая система.

задание банальное, тупо дейкстра, но тесты кривые, есть идеи КАК нужно написать программу, чтобы вывод совпал с сэмплом?

В графстве Алгоритмия построено несколько городов. Между некоторыми городами проложены дороги.

Стоимость проезда по разным дорогам разная. Известный путешественник Эдсгер Дейкстра стоит в городе X.

Он хочет узнать какое минимальное количество местных денежков придётся потратить, чтобы доехать из города X

до любого другого города.

Формат входных данных
В первой строке дано имя города, где находится Эдсгер Дейкстра (город X).
Во второй строке дано число N - количество городов в графстве
В последующих N строках описано с какими городами связан дорогами каждый из N городов графства. Каждая такая строка имеет вид:
Gi CNTi N1 S1 N2 S2 ... N CNTi SCNTi где
Gi - город, для которого даны имена городов, связанных с ним дорогами
CNTi - количество таких [соседних] городов
N1, N2, .. - их имена
S1, S2, .. - соответственно стоимость проезда по дороге из города Gi в эти города

Формат выходных данных
В единственной строке выходного файла должно быть перечислено через пробел N пар вида город стоимость_проезда_до_него. Города в строке должны быть отсортированы в порядке возрастания. Если до какого-то города нет возможности доехать, то вместо стоимости вывести inf

[input]

saratov
4
tomsk 2 saratov 5 perm 7
omsk 2 saratov 4 perm 1
saratov 3 tomsk 5 perm 12 omsk 4
perm 3 tomsk 7 saratov 12 omsk 1

[output]

tomsk 5 omsk 4 perm 5 saratov 0

50 тестов, нормальное решение проходит 0 из низ, если вывести строку "tomsk 5 omsk 4 perm 5 saratov 0",

то первый тест проходится и мы имеем 2%