Problem Description

In a certain country, there are $n$ cities, and any two cities are connected by a unique path. The length of each road connecting two cities is $z_i$.

The people of this country have an extraordinary passion for fire, making the fire safety industry the most prosperous sector. Due to the government's frustration with the high expenditure on fire safety (due to the overwhelming public enthusiasm) yet inability to act (due to high public support in presidential elections), they can only strive to enhance fire safety capabilities.

The country's budget allows for the establishment of a fire safety hub along a path (with both ends at cities) where the total length of edges does not exceed $s$. To maximize the utilization of the hub, the maximum distance from any other city to this path should be minimized.

You are in charge of this project and need to determine the optimal location for the hub.

Input Format

The input consists of $n$ lines:

• The first line contains two positive integers $n$ and $s$, separated by a space. $n$ is the number of cities, and $s$ is the upper limit of the path length. The city nodes are numbered from $1$ to $n$.
• From the second line to the $n$-th line, each line provides three positive integers separated by spaces, representing the two endpoint nodes and the length of each edge. For example, 2 4 7 indicates an edge connecting nodes $2$ and $4$ with a length of $7$.

Output Format

The output consists of a single non-negative integer, which is the maximum distance from any city to the chosen path, ensuring this value is the smallest among all possible solutions.

Sample Input and Output

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

Notes

• For $20\%$ of the data, $n \le 300$.
• For $50\%$ of the data, $n \le 3 \times 10^3$.
• For $100\%$ of the data, $1 \le n \le 3 \times 10^5$, $1 \le z_i \le 10^3$.
• Note that there are edges with a weight of $0$ in the data.

见题面 Input 部分

见题面 Output 部分