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

В каж­дой стро­ке файла за­пи­са­ны два на­ту­раль­ных числа (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.

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