Minimized Network Diameter

A network system can be modeled as an undirected connected graph, where each node represents a server and each edge represents a data cable with a given length. 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 structure is a tree. As the network administrator, you are allowed to add exactly one extra data cable (edge) of a given length L connecting any two servers (nodes). After adding this extra cable the communication distance between any two servers is the length of the shortest path in the new graph.

Your task is to choose a valid placement for this extra edge so that, among all possible choices, the maximum communication distance (i.e. the diameter of the network) is minimized. In other words, let d be the original tree diameter. By adding a new edge you may lower some distances but might also force some paths to use the new edge if it is beneficial – however, you are free to “hide” the extra edge if it worsens the diameter. It can be shown that an optimal strategy yields an answer equal to

$$\min\Bigl\{ d,\; \max\Bigl(L,\; \Bigl\lceil\frac{d}{2}\Bigr\rceil\Bigr)\Bigr\}. $$

Here the diameter d is the maximum distance between any two nodes in the original tree, and \(\lceil d/2\rceil\) is the ceiling of \(d/2\). That is, if the additional cable (of length L) is too heavy (i.e. L \ge d) then an optimal placement is to ignore its effect and leave the diameter unchanged; otherwise an optimal placement along the tree's diameter will yield a new diameter of \(\max(L, \lceil d/2\rceil)\). Your task is to compute this minimized diameter value.

Note: It is not required to show that this expression is optimal; you only need to implement a program to compute the answer from the given tree and cable length.

inputFormat

The first line contains two integers n and L (\(2 \le n \le 10^5\), \(0 \le L \le 10^9\)), where n is the number of servers (nodes) and L is the length of the extra data cable.

Each of the next n – 1 lines contains three integers u, v and w (\(1 \le u,v \le n\), \(1 \le w \le 10^9\)), indicating that there is an edge between node u and node v with length w. It is guaranteed that these edges form a tree.

outputFormat

Output a single integer – the minimized diameter of the network (i.e. the smallest possible maximum communication distance between any two servers after adding one extra edge of length L).

sample

3 2
1 2 2
2 3 3

3