Дан текстовый файл с описанием ациклического ориентированного взвешенного графа.

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

Числа L и M — номера вершин, W — вес ориентированного ребра из L в M.

Число строк файла совпадает с числом рёбер.

Между двумя вершинами не может быть более одного ребра.

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

Хотя бы один путь из 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.

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