Description

There are $n$ cities in a country. Any two of these $n$ cities are connected and have a unique path between them. Each road connecting two cities has length $z_i$.

The people of this country have a passion for flames beyond the universe, so the most prosperous industry is firefighting. Since the gov$$ernment cannot tolerate the people's enthusiasm (massive firefighting budget expenditure) yet can do nothing about it (public support in presidential elections), they can only try every means to improve firefighting capacity.

Now the country's budget is sufficient to build a firefighting hub along a path (with both endpoints being cities) whose total length is no more than $s$. To maximize the hub's utilization, it is required to minimize the maximum distance from all other cities to this path.

You are assigned to oversee this project, and of course you need to know where to place the hub.

Input Format

The input contains $n$ lines:

• Line $1$: 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. Nodes are numbered $1,2,\ldots,n$.
• From line $2$ to line $n$: each line gives $3$ positive integers, representing the two endpoints and the length of one edge. For example, 2 4 7 means the length of the edge connecting nodes $2$ and $4$ is $7$.

Output Format

Output a single non-negative integer, which is the minimal possible value of the maximum distance from any city to the chosen path.

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

5

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

5

Hint

For $20\%$ of the testdata, $n \le 300$.

For $50\%$ of the testdata, $n \le 3 \times 10^3$.

For $100\%$ of the testdata, $1 \le n \le 3 \times 10^5$, $0 \le z_i \le 10^3$.

2024/1/28 added a set of hack testdata.

Translated by ChatGPT 5