#580. 网络

网络

题目描述

一个一般的网络系统可以被描述成一张无向连通图。图上每个节点为一个服务器,连接服务器与服务器的数据线则看作图上的一条边,边权为该数据线的长度。两个服务器之间的通讯距离定义为其对应节点之间的最短路长度。

现在,考虑一个当前图结构为树的网络系统。你作为该网络系统的管理员,被要求在这个系统中加入一条给定长度的数据线。数据线可以连在任意两个服务器上。

你的任务是,求出在所有合法的方案中,通讯距离最远的两个服务器之间的最小距离。

输入格式

输入包含多组数据。对于每组数据,输入的第一行包含两个正整数 n,L n, L ,其中 n n 表示服务器个数,L L 为新加入的数据线的长度。
接下来 n1 n - 1 行,第 i i 行有三个正整数 ai,bi,li a_i, b_i, l_i ,表示有一条长度为 li l_i 的数据线连接服务器 ai,bi a_i, b_i 。服务器编号为 1n 1 \sim n
输入的末尾以两个 0 0 作为结束。

输出格式

对于每组数据,输出一行一个整数,描述在所有合法的方案中,通讯距离最远的两个服务器之间的最小距离。

样例

样例输入 1

7 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
0 0

样例输出 1

3

样例输入 2

6 26
1 2 66
2 3 11
3 4 73
2 5 77
3 6 33
10 47
1 2 86
2 3 69
3 4 41
4 5 26
5 6 41
2 7 73
3 8 77
4 9 2
5 10 65
0 0

样例输出 2

143
232

数据范围与提示

一共有 20 个测试点,编号为 120 1 \sim 20 。每个测试点为 5 分。
保证在任一测试点中,数据的组数不会超过 15,且所有数据的 n n 之和不超过数据范围中标明的 n n 的最大值的 5 倍。
保证所有的输入数据均为不超过 2311 2 ^ {31} - 1 的非负整数,保证 n1 n \geq 1
保证数据合法。

测试点 1:n10 n \leq 10
测试点 2:n50 n \leq 50
测试点 3 ~ 4:n100 n \leq 100
测试点 5:n150 n \leq 150
测试点 6 ~ 8:n600 n \leq 600
测试点 9 ~ 10:n2000 n \leq 2000
测试点 11 ~ 15:n20000 n \leq 20000
测试点 16 ~ 20:n100000 n \leq 100000