В текстовом файле содержится описание ациклического ориентированного взвешенного графа.

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

L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину M.

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

Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100.

Существование хотя бы одного такого пути гарантируется.

Для выполнения этого задания следует написать программу.

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

L < 1000, M < 1000, W < 10 000.

Количество строк в файле не превосходит 200.

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

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

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.

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