Aesthetic

Syrup the Turtle lives in a town with a layout of $N$ locations connected by $M$ roads. Locations are numbered $1, 2, \ldots, N$ and roads are numbered $1, 2, \ldots, M$. Road $i$ directly connects locations $A_i$ and $B_i$, has length $W_i$, and can be traveled in either direction. Any two locations can reach each other directly or indirectly, and no two roads share the same pair of endpoints.

Each road has its own scenery. The residents agree on how aesthetically pleasing each road is, and the roads become more aesthetic as the index grows, from road 1 to road $M$.

The residents want to refine the town further. An identical copy of a more aesthetic road is built on top of a strictly less aesthetic road. Road $j$ can be copied onto road $i$ if and only if $i < j$, and this changes the length of road $i$ to $W_i + W_j$. The residents vote for exactly one pair of roads to carry out this project.

Syrup makes frequent trips between his house at location $N$ and the main square at location $1$. Find the maximum possible length of the shortest path between locations $1$ and $N$ after the project is done.

The first line contains $N$ and $M$. Each of the next $M$ lines contains $A_i$, $B_i$, and $W_i$, describing road $i$.

Print a single integer on one line: the maximum possible length of the shortest path between locations $1$ and $N$ after the project.

$3 \le N \le 300000$

$2 \le M \le 300000$

$1 \le A_i \ne B_i \le N$

$0 \le W_i \le 10^9$