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.
~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~
The first line will contain two integers, ~N~ and ~M~.
Each of the next ~M~ lines contains 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 the length of the second-shortest path.
4 4 1 2 100 2 4 200 2 3 250 3 4 100