题目描述
Problem Description
A general network system can be described as an undirected connected graph. Each node in the graph represents a server, and the data lines connecting servers are considered as edges in the graph, with the edge weight being the length of the data line. The communication distance between two servers is defined as the length of the shortest path between their corresponding nodes.
Now, consider a network system where the current graph structure is a tree. As the administrator of this system, you are tasked with adding a new data line of a given length to the system. This data line can be connected to any two servers. Your task is to determine the minimum distance between the two servers with the farthest communication distance among all valid schemes.
Input Format
The input contains multiple sets of data. For each set of data, the first line contains two positive integers N and L, where N represents the number of servers and L is the length of the new data line.
The next N - 1 lines each contain three positive integers ai, bi, and li, indicating that there is a data line of length li connecting servers ai and bi. The servers are numbered from 1 to N.
The input ends with two 0s.
Output Format
For each set of data, output a single integer on a line, describing the minimum distance between the two servers with the farthest communication distance among all valid schemes.
Sample Input and Output
Input Sample #1
7 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
0 0
Output Sample #1
3
Input Sample #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
Output Sample #2
143
232
Notes
There are 20 test cases, numbered 1 through 20. Each test case is worth 5 points.
It is guaranteed that the number of data sets in any test case does not exceed 15, and the sum of N across all data sets does not exceed five times the maximum value of N specified in the data range.
All input data are non-negative integers not exceeding 2^31 - 1, and it is guaranteed that N ≥ 1.
The data are guaranteed to be valid.
The constraints for each given test case are as follows:
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分