路障(Roadblocks)

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例输入 #1

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

样例输出 #1

450

数据范围

样例解释：两条路径分别为 $1 \to 2 \to 4$（长度 $100+200=300$）和 $1 \to 2 \to 3 \to 4$（长度 $100+250+100=450$）。

对于 $100\%$ 的数据，$2 \le N \le 5000$，$1 \le R \le 10^5$，$1 \le D \le 5000$。