Core

Suppose T=<V,E,W> is an acyclic, connected, undirected graph(or we can call it unrooted tree), each edge has a positive weigh, we call this graph Tree Network. (V is the vertex set, E is edge set, and W is weigh set).

In the Tree Network, each pair of vertex u, v has a simple path, then the distance from u to v, written as d(u,v), is the length of a u,v-path.

Another definition is d(V,x), d(V,x)=min{d(v,x)|v∈V}.

Suppose any connected subgraph of T is T'=(V',E',W'), We called ECC(T',T)=max{d(V',u)|u∈(V-V')} is the eccentricity of T'.

Now is your turn, give you a Tree Network T and a non-negative integer S, you must find a connected subgraph of T —— T', which satisfy the sum all of the edges weigh in T' is not bigger than S and the eccentricity of T' is the least than other subgraph of T. We called the T' “Core of Tree Network”

Notice: Sometimes, T' only contains one vertex, and you may find there are many cores. But we only want to know the minimal eccentricity of T', and that is determinately.

Input includes multiple cases.

First line is the number of case x.

For each case:

The first line includes two integer numbers. N (1<=N<=10000) and S(1<=S<=108).

The other n-1 lines describe the edges in T.

Each line contains three positive integer numbers u,v,w(1<=u,v,w<=10000), describe the head, the endpoints and the weigh of an edge.

Only one integer s, the minimal eccentricity of T'.

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

5
3 

2009 Multi-University Training Contest 15 - Host by BUAA