A country has $n$ cities, and any two of these $n$ cities are connected by a unique path. The length of each road connecting two cities is $z_i$ ($z_i \le 1000$).

The people of this country have a passion for fire that transcends the universe, making the fire service the most prosperous industry in the country. Because the government cannot bear the citizens' enthusiasm (due to the massive fire service budget expenditures) but is helpless to stop it (due to the president's approval ratings), it can only try its best to improve firefighting capabilities.

Now, the country has enough funding to build a fire hub along a path (where both endpoints are cities) with a total length not exceeding $s$. To maximize the utilization of the hub, we want to minimize the maximum distance from any other city to this path.

You are tasked with overseeing this project, and you naturally need to know where the hub should be built.

Input

The input contains $n$ lines:

The first line contains two positive integers $n$ and $s$, separated by a space. Here, $n$ is the number of cities, and $s$ is the upper bound on the path length. The nodes are numbered $1, 2, \dots, n$.

From the second line to the $n$-th line, each line provides three space-separated positive integers, representing the two endpoint indices and the length of each edge, respectively. For example, "2 4 7" indicates that the length of the edge connecting node 2 and node 4 is 7.

Output

Output a single non-negative integer, which is the maximum distance from all cities to the chosen path, such that this maximum value is minimized among all possible schemes.

Constraints

For 20% of the data, $n \le 300$. For 50% of the data, $n \le 3000$. For 100% of the data, $n \le 300000$, and edge lengths are $\le 1000$.

Examples

Input 1

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

Output 1

5

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

Output 2

5