Мэг Томас оказалась в ловушке Сущности в очередном испытании.

За ней по пятам гонится маньяк с бензопилой.

Мэг нужно как можно скорее сбежать в открытые Ворота.

Карта испытания представляет собой ациклический ориентированный взвешенный граф.

В каждой строке текстового файла записаны два натуральных числа L, M и одно положительное вещественное число W. L и M — номера локаций, W — время в секундах, которое тратит Мэг на перебежку из локации L в локацию M.

Мэг начинает свой путь в локации с номером 1.

Выход в ворота находится в локации с номером 100.

Однако ворота не откроются, пока Мэг не заведёт 3 генератора.

Генераторы расположены в локациях 15, 47 и 79.

Это означает, что маршрут Мэг от стартовой точки до ворот обязан проходить через все три эти вершины.

Найдите кратчайший путь, который позволит Мэг завести все генераторы и сбежать в ворота.

Под длиной пути понимается минимальное суммарное время перебежек.

В ответе запишите целую часть найденного минимального времени.

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

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

L ≤ 1000, M ≤ 1000; W ≤ 10 000.

Количество строк в файле равно 1000.

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