Second Shortest Path

Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. Her farm consists of a network of intersections and bidirectional roads. She starts at intersection 1 and her friend is at intersection N. Instead of the shortest route, she wants to take the second-shortest path – defined as the shortest path that is strictly longer than the shortest path(s). Note that the second-shortest path may share roads or even revisit intersections that are used in the shortest path.

Constraints: $$1 \leq N \leq 5000$$ and $$1 \leq R \leq 100000$$, where R is the number of roads. Each road is described by three integers representing two intersections and the road length.

inputFormat

The first line contains two integers N and R, denoting the number of intersections and roads, respectively. Each of the following R lines contains three integers a, b, and w, which represent a bidirectional road connecting intersections a and b with length w.

outputFormat

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

sample

4 4
1 2 100
2 4 100
1 3 100
3 4 100

400