Маршрут через обязательное ребро
Во входных данных содержится описание ациклического ориентированного взвешенного графа. Каждая строка задаёт одно ребро: в ней записаны номера вершин и и вес ребра, ведущего из вершины в вершину . Любые две вершины соединены не более чем одним ребром.
Найдите целую часть длины кратчайшего пути из вершины с номером в вершину с номером , содержащего ребро, которое ведёт из вершины с номером в вершину с номером . Под длиной пути понимается сумма весов рёбер, составляющих путь. Существование хотя бы одного такого пути гарантируется.
Входные данные
Входные данные содержат не более строк; читать их нужно до конца ввода. В каждой строке записаны два натуральных числа и и положительное вещественное число (, , ). Числа в строке разделены произвольным ненулевым количеством пробелов и (или) табуляций.
Вершины графа могут быть пронумерованы не подряд, а ребро может вести в вершину с меньшим номером. Вес записан ровно с одной цифрой после десятичной точки.
Гарантируется, что длина искомого пути не является целым числом.
Выходные данные
Выведите одно целое число — целую часть длины кратчайшего из таких путей.
Примеры
11 53 1.1 53 97 1.3 53 29 2.5 29 97 2.1 11 97 0.5
5
11 53 1.1 53 29 2.5 29 97 2.1 53 20 0.1 20 29 0.1
5
Примечание
В обоих примерах подходящий путь проходит через вершины 11, 53, 29 и 97. Его длина равна , ответ — 5. Во втором примере переход из 53 в 29 через вершину 20 не заменяет обязательное ребро: такой путь не подходит.