Анализ графов

(Л. Шастин) В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вершин графа, W – вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром. Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 2691 в вершину с номером 9514 при условии, что первое ребро найденного пути ведет из вершины 2691 в вершину 2840, а последнее ребро — из вершины 9180 в вершину 9514. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, входящих в него. Для выполнения этого задания следует написать программу. Вершины графа могут быть пронумерованы не подряд. L ≤ 10000, M ≤ 10000; W ≤ 100. Количество строк в файле не превосходит 100 000. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле для графа на рисунке.

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 При условии поиска длины кратчайшего пути из вершины с номером 6 в вершину с номером 12, в котором первое ребро ведет из вершины №6 в вершину №1, а последнее из вершины №100 в вершину №12, для приведённого примера верным ответом будет 9. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла