Кратчайший путь
Во входных данных содержится описание ациклического ориентированного взвешенного графа. Каждая строка задаёт одно ребро: в ней записаны номера вершин и и вес ребра, ведущего из вершины в вершину . Любые две вершины соединены не более чем одним ребром.
Найдите целую часть длины кратчайшего пути из вершины с номером в вершину с номером . Под длиной пути понимается сумма весов рёбер, составляющих путь. Существование хотя бы одного такого пути гарантируется.
Входные данные
Входные данные содержат не более строк; читать их нужно до конца ввода. В каждой строке записаны два натуральных числа и и положительное вещественное число (, , ). Числа в строке разделены произвольным ненулевым количеством пробелов и (или) табуляций.
Вершины графа могут быть пронумерованы не подряд, а ребро может вести в вершину с меньшим номером. Вес записан ровно с одной цифрой после десятичной точки.
Гарантируется, что длина искомого пути не является целым числом.
Выходные данные
Выведите одно целое число — целую часть длины кратчайшего пути.
Примеры
100 12 1.0 6 7 7.0 6 1 1.0 1 7 5.5 7 100 2.0 4 100 8.0 1 100 12.0 1 4 2.5
7
1 5 3.2 5 100 4.1 1 100 7.9 5 9 1.0 9 100 2.5
6
Примечание
В первом примере кратчайший путь имеет длину , её целая часть равна . Путь длиннее: .
Во втором примере кратчайший путь состоит из трёх рёбер: , его длина .