Let $T=(V,E,W)$ be an acyclic and connected undirected graph (also known as an unrooted tree), each edge has a positive integer weight, we call $T$ a tree network, where $V,E$ Respectively represent the collection of nodes and edges, $W$ represents the collection of the length of each side, and let $T$ have n nodes.

Definitions

• Path: There is a unique simple path between any two nodes $a$ and $b$ in the tree network. Let $d(a,b)$ represent the length of the path with a and b as the endpoints, which is the sum of the lengths of the sides on the path. We call $d(a,b)$ the distance between two nodes $a,b$. The distance from a point $v$ to a path P is the distance from that point to the nearest node on P: $d(v,P)=min\{d(v,u),\text{u is the node on the path P}\}$

• Diameter of the tree network: The longest path in the tree network is called the diameter of the tree network. For a given treenet $T$, the diameter is not necessarily unique, But it can be proved that the midpoint of each diameter (not necessarily exactly a certain node, it may be inside a certain side) is unique, and we call this point the center of the tree network.

• Eccentric distance $ECC(F)$: the distance from the node farthest from the path $F$ in the tree network T to the path $F$, that is $ECC(F)=max\{d(v,F),v\in V\}$

Task

For a given tree network $T=(V,E,W)$ and a non-negative integer $s$, find a path $F$, which is a path on a certain diameter (both ends of the path are nodes in the tree network) , whose length does not exceed $s$ (can be equal to $s$), so that the eccentricity $ECC(F)$ is the smallest. We call this path the core of the tree network $T=(V,E,W)$. When necessary, $F$ can degenerate to a node. Generally speaking, under the above definition, there is not necessarily only one core, but the minimum eccentricity is unique.

The figure below shows an example of a tree network. In the figure, $A-B$ and $A-C$ are two diameters with a length of 20. Point $W$ is the center of the treenet, and the length of the $EF$ edge is $5$. If $s=11$ is specified, the core of the tree network is path $DEFG$ (or path $DEF$), and the eccentricity is $8$. If $s=0$ (or $s=1$ or $s=2$), the core of the tree network is node $F$ with an eccentricity of $12$.

Input Specification

• Line $1$, two positive integers $n$ and $s$, separated by a space. $n$ is the number of nodes in the tree network, and $s$ is the upper bound of the length of the core of the tree network. Let the node numbers be $1,2,\dots n$.
• Lines $2$ to $n$ each contains 3 positive integers separated by spaces, indicating the two endpoint numbers and length of each edge in turn. For example, 2 4 7 means that the length of the edge connecting nodes $2$ and $4$ is $7$.

It's guaranteed that the input forms a valid tree.

Output Specification

One non-negative numbers, the minimum eccentricity under this condition.

Sample Input 1

5 2 
1 2 5 
2 3 2 
2 4 4 
2 5 3

Sample Output 1

5

Sample Input 2

8 6 
1 3 2 
2 3 2 
3 4 6 
4 5 3 
4 6 4 
4 7 2 
7 8 3

Sample Output 2

5

Constraints

• $32\mathrm{\%}$ of the test cases satisfy $5\le n\le 15$.
• $56\mathrm{\%}$ of the test cases satisfy $5\le n\le 80$.
• $80\mathrm{\%}$ of the test cases satisfy $5\le n\le 300$, $0\le s\le 1000$.
• $90\mathrm{\%}$ of the test cases satisfy $5\le n\le 5\times {10}^5$, $0\le s<2^{31}$, and all lengths are positive integers not exceeding $1000$.
• $100\mathrm{\%}$ of the test cases satisfy $5\le n\le 2\times {10}^6$, $0\le s<2^{31}$, and all lengths are positive integers not exceeding $1000$.