描述

贝茜（Bessie）搬到了一个小农场，有时会回去拜访她最好的朋友之一。她不想太快到达她的旧家，因为她喜欢沿途的风景。她决定选择次短路径而非最短路径。她知道一定存在这样的次短路径。

乡村由$R$（$1 \leq R \leq 100,000$）条双向道路组成，每条道路连接$N$（$1 \leq N \leq 5,000$）个交叉路口中的某两个，这些路口编号为$1$至$N$。贝茜从路口$1$出发，她的朋友（目的地）位于路口$N$。

次短路径可以与任意最短路径共享部分道路，并且允许回溯（即重复经过同一条道路或同一个路口）。次短路径的定义是：在所有比最短路径长的路径中，长度最短的那一条（即如果存在多条最短路径，次短路径的长度必须严格大于最短路径，但不长于其他任何路径）。

输入

• 第1行：两个用空格分隔的整数$N$和$R$
• 第2..$R+1$行：每行包含三个用空格分隔的整数$A$、$B$和$D$，表示一条连接路口$A$和$B$的道路，长度为$D$（$1 \leq D \leq 5000$）

输出

• 第1行：路口$1$到路口$N$的次短路径的长度

输入样例 1

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

输出样例 1

450  

提示

两条可能的路径：

1. $1 \rightarrow 2 \rightarrow 4$（长度$100 + 200 = 300$）
2. $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$（长度$100 + 250 + 100 = 450$）

其中最短路径的长度是$300$，次短路径的长度是$450$。

来源

USACO 2006 November Gold