Description

Bessie 搬到了一个小农场，有时喜欢回去拜访她的一个好朋友。她不想太快到达她的旧家，因为她喜欢沿途的风景。她决定选择第二短的路径而不是最短的路径。她知道一定存在某条第二短路径。

乡村由 $R(1\le R\le100,000)$ 条双向道路组成，每条道路连接 $N(1\le N\le5000)$ 个交叉路口中的两个，这些交叉路口被方便地编号为 $1$ 到 $N$。Bessie 从交叉路口 $1$ 出发，她的朋友（目的地）在交叉路口 $N$。

第二短路径可以与任何最短路径共享道路，并且可以回溯，即多次使用相同的道路或交叉路口。第二短路径是长度比最短路径长的最短路径（即，如果存在两条或多条最短路径，第二短路径是长度比这些路径长但不比任何其他路径长的路径）。

Input Format

第 $1$ 行：两个用空格分隔的整数：$N$ 和 $R$。

第 $2$ 行到第 $R+1$ 行：每行包含三个用空格分隔的整数：$A$、$B$ 和 $D$，描述连接交叉路口 $A$ 和 $B$ 的一条长度为 $D(1\le D\le5000)$ 的道路。

Output Format

第 $1$ 行：节点 $1$ 和节点 $N$ 之间第二短路径的长度。

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

450

Hint

两条路径：$1\to2\to4$（长度 $100+200=300$）和 $1\to2\to3\to4$（长度 $100+250+100=450$）。

（由 ChatGPT 4o 翻译）