题目描述

每天早晨，$\red{FJ}$从家中穿过农场走到牛棚。农场由 $\red{N }$块农田组成，农田通过 $\red{M }$条双向道路连接，每条路有一定长度。$\red{FJ }$的房子在 $\red{1 }$号田，牛棚在 $\red{N }$号田。没有两块田被多条道路连接，以适当的路径顺序总是能在农场任意一对田间行走。当$\red{FJ}$从一块田走到另一块时，总是以总路长最短的道路顺序来走。

$\red{FJ }$的牛呢，总是不安好心，决定干扰他每天早晨的计划。它们在 $\red{M }$条路的某一条上安放一叠稻草堆，使这条路的长度加倍。牛希望选择一条路干扰使得$\red{FJ }$从家到牛棚的路长增加最多。它们请你设计并告诉它们最大增量是多少。

输入格式

第 $\red{1 }$行：两个整数 $\red{N, M}$。

第 $\red{2 }$到 $\red{M+1 }$行：第 $\red{i+1 }$行包含三个整数 $\red{A_i, B_i, L_i，}$$\red{A_i }$和 $\red{B_i }$表示道路 $\red{i }$连接的田的编号，$\red{L_i }$表示路长。

输出格式

第 $\red{1 }$行：一个整数，表示通过使某条路加倍而得到的最大增量。

样例

输入样例

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

输出样例

2

提示

若使 $\red{3 }$和 $\red{4 }$之间的道路长加倍，最短路将由 $\red{1-3-4-5 }$变为 $\red{1-3-5}$。

对于 $\red{30\%}$的数据，$\red{N <= 70，}$$\red{M <= 1,500}$。

对于 $\red{100\%}$的数据，$\red{1 <= N <= 100，}$$\red{1 <= M <= 5,000，}$$\red{1 <= L_i <= 1,000,000}$。