Description

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

Input

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

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

1 2 2

2 4 4

2 3 3

3 4 4

Sample 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%的数据，1 <= z <= 5000，z 表示无向边的边长。