The Zerg, having held off the Protoss timing attack, is preparing to counterattack! However, they don't wish to be all that obvious, so they will not take the shortest path to the Protoss natural to counterattack. Instead, they will take the second-shortest path! It is guaranteed there are at least two paths with distinct lengths.

To be clear about what this means, we model the map the Zerg is on as an undirected weighted graph. Let $L_1$ be the length of the shortest path from vertex $1$ to vertex $N$. The Zerg is looking for the smallest realizable path length $L_2>L_1$. The Zerg army must start at vertex $1$ and end up at vertex $N$, only traveling along edges in the graph. The Zerg army must traverse an edge in its entirety, but is allowed to visit vertices more than once or reuse edges.

Constraints

$2\le N\le 5\cdot {10}^3$

$1\le M\le {10}^5$

$1\le A_i,B_i\le N$

$1\le W_i\le 5\cdot {10}^3$

Input Specification

The first line will contain two integers, $N$ and $M$.

Each of the next $M$ lines will contain three space-separated integers, $A_i$, $B_i$ and $W_i$, indicating there is an undirected edge between vertices $A_i$ and $B_i$ with length $W_i$.

Output Specification

Output the length of the second-shortest path.

Sample Input

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

Sample Output

450