Description

每天早晨，约翰都要横穿整个农场，从自己的家里走到牛棚。已知农场由n个点构成（1<=n<=250），有m条小路相连（1<=m<=25000，且路都是双向的）。约翰的家在点1，牛棚在点n。两个点直接最多只有一条路相连，从一个点到另一个点可能需要经过其他的点。约翰总是通过最短的路从家里走到牛棚。

奶牛们喜欢恶作剧，所以它们盘算着在某一条路上放一个巨大的障碍，让这条路的路程变为两倍。而且，奶牛们希望约翰从家里走到牛棚的距离尽可能长。请你帮助奶牛们解决这个问题，并输出约翰的路程增加了多少。

Format

Input

第一行输入两个整数n和m；

接下来m行，每行输入三个整数x y z，表示点x和点y之间的距离是z（1<=z<=10^6）

Output

输出约翰增加的路程。

Samples

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

2

Hint

在奶牛没有捣乱的情况下，约翰每天走的路是1->3->4->5，路程为6；

奶牛可以在点3到点4的路上增加障碍物（3到4的距离变为6），约翰的路成变为1->3->5，路程为8，因此路程增加了2。