Roadblocks

Bessie has moved to a small farm and sometimes likes to walk back to visit one of her best friends. She does not want to arrive too quickly, because she enjoys the scenery along the way, so she has decided to travel the second-shortest path instead of the shortest one. Such a path is guaranteed to exist.

The countryside has $N$ intersections, numbered $1$ through $N$, connected by $R$ bidirectional roads. Each road joins two intersections and has a positive length. Bessie starts at intersection $1$, and her friend lives at intersection $N$.

A path here is any walk from $1$ to $N$: it may reuse roads or intersections, and it may even backtrack over a road it has already used. The length of a path is the sum of the lengths of the roads it uses. The second-shortest path is a path whose length is strictly greater than the length of the shortest path, yet no greater than the length of any other such path. In other words, if $L$ is the shortest achievable length, the answer is the smallest achievable length that is strictly larger than $L$. (If several different routes share the shortest length $L$, they all count as shortest; the second-shortest length is still the next larger achievable value.)

Constraints: $1 \le N \le 5000$ and $1 \le R \le 100{,}000$.

• Line 1: two space-separated integers $N$ and $R$.
• Lines 2 to $R+1$: each line contains three space-separated integers $A$, $B$, and $D$, describing a bidirectional road between intersections $A$ and $B$ with length $D$ ($1 \le D \le 5000$).

• Print a single line containing the length of the second-shortest path from intersection $1$ to intersection $N$.

In the sample, the shortest path is $1 \to 2 \to 4$ with length $100 + 200 = 300$, and the next-longer path is $1 \to 2 \to 3 \to 4$ with length $100 + 250 + 100 = 450$, so the second-shortest length is $450$.