跑跑跑

有一天Morning_X觉得自己太水了，于是他觉得锻炼一下自己的水题能力，

但是好的水题能力需要一个好的身体才可以（水题很费脑子的），于是Morning_X决定锻炼一下自己 的身体

于是Morning_X决定每天早起绕着学校晨跑（真特么让人害怕），他将学校的一些建筑标志成n个点，这样子学校就变成了一个n个点构成的图

且每个点都是双向联通。于是Morning_X就开始牛逼哄哄的开始了晨跑计划。

但是大家都知道Morning_X是个懒逼，于是他想要偷偷的写了一个算法来让自己能够从第一个建筑开始通过最少的体力消耗到达第n号楼。

然而恶心自有恶人磨，他的小心思被大佬Seventh发现，于是Seventh偷偷的改了他的程序，但是因为不能让Morning_X发现，于是他只改动了一点

他能够在一条路上面让Morning_X的体力消耗加倍。

现在处于上帝视角的你们，请告诉Seventh大佬，要在哪条路使体力消耗加倍，能够让Morning_X的消耗最大，你只需要告诉Seventh大佬最多能使Morning_X的体力消耗增加多少即可

单组数据

第一行输入两个整数n，m，表示有多少个点，以及道路数量（2 <= n <= 250，1 <= m <= 250000）
接下来m行，

每行三个整数，分别表示哪两个点相通和这条道路上Morning_X消耗的体力。

输出一个整数，表示Seventh能够让Morning_X消耗体力增大的最大值。

5 9
1 2 3
1 3 2
1 4 5
1 5 12
2 3 1
2 4 6
3 4 7
3 5 6
4 5 1

2
对于样例，Morning_X原先的最短路程为6，Seventh将第3条边加倍，会使最短路程变为8