题目描述

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

乡村由 $R$ 条双向道路组成，每条道路连接 $N$ 个交叉路口中的两个，这些交叉路口被编号为 $1$ 到 $N$。Bessie 从交叉路口 $1$ 出发，她的朋友在交叉路口 $N$。

第二短路径可以与任何最短路径共享道路，并且可以回溯，即多次使用相同的道路或交叉路口。第二短路径是长度严格大于所有最短路径的最短路径（如果存在多条最短路径，则第二短路径是比它们都长的最短的路径）。

输入格式

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

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

输出格式

一行一个整数，表示从交叉路口 $1$ 到交叉路口 $N$ 的第二短路径的长度。

样例

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

450

样例解释
两条路径：$1\to2\to4$（长度 $100+200=300$）是最短路径；$1\to2\to3\to4$（长度 $100+250+100=450$）是第二短路径。

数据范围

• $1 \le N \le 5000$
• $1 \le R \le 100\,000$
• $1 \le A, B \le N$
• $1 \le D \le 5000$