题目描述

每天早晨，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$ 表示路长。

输出格式

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

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

2

提示

【样例说明】

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

【数据规模和约定】

对于 $30\%$ 的数据，$N \le 70，M \le 1500$。

对于 $100\%$ 的数据，$1 \le N \le 100，1 \le M \le 5,000，1 \le L_i \le 1,000,000$。