Задача #420

(А. Игнатюк) Представлена карта метро в виде таблицы, которая содержит в себе номера станций (уникальные ID) и расстояния до ближайших из них, считая от конкретного номера станции.

На карте представлена следующая схема формы записи:

6

3 20 17

6 15 16

7 17 40

5 19 81

9 21 13

11 14 18

Первое число N (1 < N < 300) обозначает количество работающих станций. Далее имеется N строк, содержащих по 3 числа, разделенных пробелом. Первое число в идущих ниже строках обозначает текущий уникальный ID-номер станции, а последующие два числа (всегда различных по величине) указывают на расстояние до станций, ID которых численно отличаются на 1 и 2 в большую сторону соответственно. По имеющимся данным необходимо узнать, до какой станции с максимальным ID-номером можно доехать, если начинать со станции, имеющей наименьший ID, и какое минимальное расстояние можно преодолеть, если при поездке на каждую следующую возможную станцию необходимо всегда выбирать кратчайший маршрут. В качестве ответа указать два числа - сначала минимальное расстояние, а затем номер станции.

Примечание: передвигаться можно только на те станции, ID-номера которых существуют (присутствуют в наборе, в файле).

Приведем решение задачи для примера выше. Из станции 3 можно отправиться на станцию 4 или 5, но поскольку станции с ID = 4 нет, то поехать можно только на станцию c ID = 5, преодолев при этом 17 километров. Из пункта 5 можно отправиться в пункт 6 или 7. Так как до пункта 6 можно добраться, преодолев наименьшее количество километров (19 < 81), выбирается станция с ID = 6. От этой станции можно поехать либо на станцию с ID = 8, либо на станцию с ID = 7. Поскольку станция с ID = 8 отсутствует в списке, необходимо переместиться на станцию с ID = 7, преодолев 15 километров. От станции с ID = 7 передвигаемся на станцию с ID = 9, а затем на станцию с ID = 11. Итого между станциями было пройдено 17 + 19 + 15 + 40 + 13 километров.

Ответ к примеру: 104 11.