Bessie 搬到了小农场，有时喜欢回去看一位好友。她喜欢沿途风景，不想太快回到旧家，因此决定走次短而非最短路。她知道一定存在次短路。

乡间有 $R$ 条双向道路（$1 \le R \le 100,000$），每条连接 $N$ 个路口（$1 \le N \le 5000$）中的两个，路口编号 $1..N$。Bessie 从1号出发，朋友在终点 $N$。

次短路可以与任一最短路共用道路，也可折返，多次经过同一道路或路口。它是长度严格大于最短路的最短路径；若有多个最短路，次短路比它们长，但不比任何其他路径更长。

输入格式

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

第 $2..R+1$ 行：每行三个空格分隔整数 $A$、$B$、$D$，表示连接路口 $A$ 与 $B$、长度 $D$（$1 \le D \le 5000$）的道路。

输出格式

第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$）。