#2161. Roadblock

Roadblock

题目描述

每天早晨,FJ\red{FJ}从家中穿过农场走到牛棚。

农场由 N\red{N }块农田组成,农田通过 M\red{M }条双向道路连接,每条路有一定长度。

FJ\red{FJ }的房子在 1\red{1 }号田,牛棚在 N\red{N }号田。没有两块田被多条道路连接,以适当的路径顺序总是能在农场 任意一对田间行走。

FJ\red{FJ}从一块田走到另一块时,总是以总路长最短的道路顺序来走。

FJ\red{FJ }的牛呢,总是不安好心,决定干扰他每天早晨的计划。它们在 M\red{M }条路的某一条上安放一叠稻草堆,使这条路的长度加倍。

牛希望选择一条路干扰使得FJ\red{FJ }从家到牛棚的路长增加最多。

它们请你设计并告诉它们最大增量是多少。

输入格式

1\red{1 }行:两个整数 N,M\red{N, M}

2\red{2 }M+1\red{M+1 }行:第 i+1\red{i+1 }行包含三个整数 Ai,Bi,Li\red{A_i, B_i, L_i,}Ai\red{A_i }Bi\red{B_i }表示道路 i\red{i }连接的田的编号,Li\red{L_i }表示路长。

输出格式

1\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