After a successful expedition for a marathon at UFG, the competitors AlbertoTDNeto, duduFreire, EYZ, henriqueramos.qs, and MagePetrus made a pact: every time the 5 of them meet, they must roll a D100 (100-sided die). If the rolled number is 100, they must immediately go to Goiânia.

After many meetings, this finally happened, and the competitors will keep their promises. They all get into Henrique's car, which will drive them to Goiânia. The marathon runners want to take the shortest possible route from Brasília to Goiânia, of course. Additionally, since the car is quite heavy, Henrique is worried about the possibility of running out of fuel in the middle of the road. So, among the shortest paths, he wants a path that minimizes the longest distance the car will travel between two gas stations.

The gas stations are numbered from $$$1$$$ to $$$N$$$. Henrique will start from Brasília at gas station number $$$1$$$ and will finish his journey at gas station number $$$N$$$, in Goiânia. There are $$$M$$$ roads connecting pairs of distinct gas stations. For each $$$i$$$ from $$$1$$$ to $$$M$$$, road number $$$i$$$ starts from gas station $$$a_i$$$, leads to gas station $$$b_i$$$, and has a length of $$$w_i$$$ kilometers. It is only possible to travel this road in the direction from $$$a_i$$$ to $$$b_i$$$. It is guaranteed that there is a path from $$$1$$$ to $$$N$$$.

Help Henrique find a shortest path that minimizes the longest distance traveled between two consecutive gas stations.