Задача #6747

(А.Богданов) В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вершин графа, W – вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 3 в вершину с номером 97, проходящего сначала через вершину 25, а затем через вершину 50. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.

Гарантируется: L, M ≤ 1000, W ≤ 10 000, число строк ≤ 200. Нумерация вершин может быть не сплошной. Числа в строке разделены произвольным числом пробелов и/или табуляций.