MINDIST - Minimum Distance

Given an weighted tree, you are to find two nodes A and B of the tree (A and B needn't be different), such that the length of the path between A and B is less than or equals to a given integer S, and the maximum distance from each node of the tree to this path is minimum.

Input

The first line of the input contains a single integer T, the number of test cases. T blocks follow.

For each test case, the first line contains two space-separated integer N (1<=N<=100000) and S (0<=S<=100000000).N-1 lines follow, each contains three integers X (1<=X<=N), Y (1<=Y<=N) and Z (1<=Z<=1000), denotes that there is an (undirected) edge weighted Z between node X and Y. The input is correct.

Output

T lines, each contains a single integer denoted the minimum distance.

Example

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

Output:
5
5
Warning: large input/output data, be careful with certain languages

Added by:Fudan University Problem Setters
Date:2007-11-19
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:description by Blue Mary; standard program and test data by g201513

hide comments
2024-09-11 17:15:14
Worth looking at for Python users struggling to parse the input https://stackoverflow.com/questions/78974186/sphere-online-judge-spoj-python-input-handling-broken/78974552#78974552
2024-09-11 12:03:26
Additional Test Case:
Input
1
5 30
1 2 50
2 4 40
2 3 40
2 5 30

Output
50
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.