#1014. 「USACO 2011.12 Silver」Roadblock

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
rblock.in ≫ rblock.out
题目类型
传统
评测方式
文本比较
上传者 admin

显示标签

题目描述

View problem

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

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

输入格式 rblock.in

行:两个整数

行:第 行包含三个整数 表示道路 连接的田的编号, 表示路长。

输出格式 rblock.out

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

样例

输入

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

输出

2

解释

若使 之间的道路长加倍,最短路将由 变为

数据范围与提示

对于 的数据,

对于 的数据,