Description

A general network system can be described as an undirected connected graph. Each node is a server; each edge represents a data cable connecting two servers, and the edge weight equals the length of that cable. The communication distance between two servers is defined as the length of the shortest path between their corresponding nodes.

Now consider a network system whose current graph structure is a tree. As the administrator of this network system, you are required to add one new data cable of a given length to this system. The cable can connect any two servers. Your task is to find, among all valid plans, the minimum possible distance between the farthest pair of servers.

Input Format

The input contains multiple test cases. For each test case, the first line contains two positive integers $N, L$, where $N$ is the number of servers and $L$ is the length of the new data cable.

The next $N - 1$ lines, the $i$-th line contains three positive integers $a_i, b_i, l_i$, indicating there is a data cable of length $l_i$ connecting servers $a_i$ and $b_i$. Servers are numbered $1 \sim N$.

The input ends with 0 0.

Output Format

For each test case, output one line with a single integer: the minimum possible distance between the farthest pair of servers over all valid plans.

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

3

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

143
232

Hint

There are $20$ test points, numbered $1 \sim 20$. Each test point is worth $5$ points.

It is guaranteed that, within any single test point, the number of groups of testdata does not exceed $15$, and the sum of $N$ over all testdata does not exceed $5$ times the maximum $N$ specified in Constraints.

All input numbers are non-negative integers not exceeding $2^{31} - 1$, and $N \geq 1$.

All testdata are valid.

For the given test points, their constraints are shown in the table below.

Translated by ChatGPT 5