Description

　　破了魔法阵后，亮亮进入了一座迷宫。这座迷宫叫做“梦境迷宫”，亮亮只有走出这座迷宫，才能从睡梦中醒来。
　　梦境迷宫可以用无向图来表示。它共有 n 个点和 m 条双向道路，每条道路都有边权，表示通过这条道路所需的时间， 且每条道路可以多次经过。 亮亮位于一号点， 而出口则是 n 号点。原本，亮亮该找到一条最短路，快速冲出迷宫，然而，梦境迷宫的特殊之处在于，如果沿着最短路到达出口，亮亮就会永远陷入梦境。因此，亮亮必须寻找一条次短路。次短路的长度须严格大于最短路（可以有多条）的长度，同时又不大于所有除最短路外的道路的长度。
　　你的任务，就是编写一个程序，帮助亮亮找到通向出口的次短路。

Fomat

Input

　　第一行有两个整数 n、m，表示迷宫内共有 n 个点，m 条边。
　　接下来 m 行，每行三个整数 x、y、z，表示结点 x 和 y 之间连有一条边权为 z 的无向边。

Output

　　一个整数，表示次短路的长度。

Sample 1

Input

4 4
1 2 2
2 4 4
2 3 3
3 4 4

Output

9

Hint

【样例解释】
　　最短路：1 -> 2 -> 4 (长度为 2+4=6)
　　次短路：1 -> 2 -> 3 -> 4 (长度为 2+3+4=9)
【数据范围】
　　对于 100%的数据，1 <= n <= 5000，1 <= m <= 100,000。
　　对于 100%的数据，0 <= z <= 5000，z 表示无向边的边长。