rt

题目描述

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

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

输入格式

第 $1$ 行：两个整数 $N$, $M$。

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

2

提示

【样例说明】

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

【数据规模和约定】

对于 30% 的数据，N <= 70，M <= 1,500。

对于 100%的数据，1 <= N <= 100，1 <= M <= 5,000，1 <= L_i <= 1,000,000。

---

改的可能不太好，但是比原题清晰很多