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

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

【样例说明】 若使 $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$。

USACO 2011 December Contest, Silver Division