A general network system can be described as an undirected connected graph. Each node in the graph represents a server, and the data cables connecting servers are represented as edges with weights equal to the lengths of the cables. 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 structure is a tree. As the administrator of this network, you are required to add one new data cable of a given length to the system. The data cable can be connected between any two servers.

Your task is to find the minimum possible value of the maximum communication distance between any two servers among all valid connection schemes.

Input

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

The next $n - 1$ lines each contain three positive integers $a_i, b_i, l_i$, representing a data cable of length $l_i$ connecting servers $a_i$ and $b_i$. The servers are numbered from $1$ to $N$.

The input is terminated by two $0$s.

Output

For each test case, output a single integer representing the minimum possible value of the maximum communication distance between any two servers among all valid connection schemes.

Examples

Input 1

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

Output 1

3

Input 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 2

143
232

Input 3

See sample data download.

Constraints

There are 20 test cases in total, numbered $1$ to $20$. Each test case is worth 5 points.

It is guaranteed that for any test case, the number of data sets does not exceed $15$, and the sum of $N$ over all data sets does not exceed $5$ times the maximum $N$ specified in the constraints.

It is guaranteed that all input data are non-negative integers not exceeding $2^{31}-1$, and $N \geq 1$.

It is guaranteed that the input data is valid.

The constraints for each test case are shown in the table below.