Задание выполняется с использованием прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа — схемы резервных каналов связи Кибер-Особняка.

В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W).

L и M — номера узлов (вершин графа), W — задержка сигнала (вес ребра), ведущего из узла L в узел M.

Сигнал может передаваться только в указанном направлении.

Две вершины графа не могут быть соединены более чем одним ребром в одном направлении.

Под длиной пути понимается минимальная сумма весов рёбер, составляющих путь.

Вершины графа могут быть пронумерованы не подряд.

L ≤ 1000, M ≤ 1000; W ≤ 100.

Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Чтобы перехватить управление голограммами, Скуби-Ду должен проложить кратчайший (с минимальной суммарной задержкой) маршрут от стартового терминала 1 до выходного узла 1000.

Известно, что канал 213→255 заблокирован Цифровым Фантомом, поэтому маршрут не должен проходить через это ребро.

Найдите подходящий под эти условия кратчайший маршрут.

В ответе запишите целую часть длины самого долгого (максимального по весу) канала, который входит в этот маршрут.