A6187 | $RoadBlock S$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

每天早晨，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

C++ 编辑器

输入

输出