Core of a Tree Network

Consider a treenetwork which is an undirected, connected, acyclic graph T=(V,E,W) with n nodes. Every edge has a positive integer weight. For any two vertices a and b, there is a unique simple path between them. Let d(a,b) denote the sum of edge‐lengths on the path between a and b (we call it the distance between a and b).

For any vertex v and any path P (where every vertex on P is a vertex in T), define $$D(v,P)=\min\{d(v,u):u \in P\}\,,$$

and the eccentricity of P in T is defined by

A diameter of the tree is a longest path in T (note that the diameter may not be unique) and it can be proved that the mid‐points of all diameters (which might lie in the interior of an edge) are unique; this unique point is called the center of T.

For a given treenetwork T=(V,E,W) and a nonnegative integer s, a core of T is defined as a path F satisfying the following conditions:

• F is a contiguous subpath of some diameter of T (its two endpoints are vertices of T). Note that F may degenerate to a single vertex.
• The length of F does not exceed s (i.e. it is at most s).
• The value \(\mathrm{ECC}(F)\) is minimized over all such possible paths. (Although there may be more than one core path, the minimum eccentricity is unique.)

For example, in the figure below (not shown), there are two diameters each of length 20. If s = 11, one optimal core is the path DEFG (or DEF), with eccentricity 8. If s = 0 (or 1 or 2), the core degenerates to vertex F and the eccentricity is 12.

Your task is to compute the minimum achievable eccentricity value by choosing an appropriate path F satisfying the above conditions.

inputFormat

The first line contains two integers n and s (1 ≤ n ≤ 200, 0 ≤ s ≤ 10^9) representing the number of vertices and the maximum allowed length of the subpath, respectively.

Each of the following n-1 lines contains three integers u, v, w (1 ≤ u,v ≤ n, 1 ≤ w ≤ 10^9) indicating that there is an edge between vertices u and v with weight w.

The input graph is guaranteed to be a tree.

outputFormat

Output a single integer which is the minimum possible value of \(\mathrm{ECC}(F)\) for a valid core F of the given tree network.

sample

3 0
1 2 3
2 3 4

4