Description

Original source: USACO 2006 Nov. Gold

Bessie has moved to a small farm, but she often returns to FJ's farm to visit her friends. Bessie enjoys the scenery along the way and doesn't want her journey to end too quickly, so every time she returns to the farm, she chooses the second-shortest path instead of the shortest one, as we are accustomed to.

The rural area where Bessie lives has $R(1 \le R \le 10^5)$ bidirectional roads, each connecting two of the $N(1 \le N \le 5000)$ farms. Bessie lives on farm $1$, and her friends live on farm $N$ (the destination of each of Bessie's trips).

The second-shortest path Bessie chooses may include any road that appears in the shortest path, and a road can be traversed multiple times. Of course, the length of the second-shortest path must be strictly greater than the length of the shortest path (there may be multiple shortest paths), but it must not exceed the length of any other path except the shortest ones.

In one sentence: Given an undirected graph, find the length of the strictly second-shortest path.

Input Format

The first line of the input file contains two integers, $N$ and $R$, separated by a space;

Lines $2$ to $R+1$: Each line contains three integers $A$, $B$, and $D$, separated by spaces, indicating a road of length $D(1\le D \le 5000)$ connecting farms $A$ and $B$.

Output Format

Output a single integer, representing the length of the second-shortest path from farm $1$ to farm $N$.

Sample 1

Shortest path: $1 \rightarrow 2 \rightarrow 4$ (length $100+200=300$) Second-shortest path: $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ (length $100+250+100=450$)

4 4
1 2 100
2 4 200
2 3 250
3 4 100

450