Optimal Fire Station Hub

Consider a country with \(n\) cities forming a tree, i.e. any two cities are connected by a unique simple path. Each road connecting two cities has a positive length \(z_i\). The government can afford to build a fire station hub along a contiguous path (whose endpoints are cities) whose total length does not exceed \(s\). The goal is to choose a path (subject to the cost limit) so that the maximum distance from any city to the nearest point on the chosen path is as small as possible.

Formally, let \(P\) be a path in the tree with total length \(\le s\). For any city \(v\) let \(d(v,P)\) denote the distance (in the tree) from \(v\) to the closest point on \(P\). You are to choose \(P\) so as to minimize \(\max_{v}\, d(v,P)\). The answer is this minimized maximum distance.

It can be shown that there is an optimal solution where \(P\) lies on a diameter of the tree. You may assume that \(1 \le n \le 2000\) and all road lengths are positive integers.

Note: All formulas are in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(s\) \((1 \le n \le 2000,\ s \ge 0)\) representing the number of cities and the maximum allowed total length of the hub, respectively. Each of the next \(n-1\) lines contains three integers \(u\), \(v\), \(z\) \((1 \le u,v \le n,\ z > 0)\) indicating that there is a road between cities \(u\) and \(v\) of length \(z\).

outputFormat

Output a single integer representing the minimized maximum distance from any city to the chosen fire station hub's path.

sample

4 1
1 2 1
2 3 1
2 4 1

1