Problem Description
Lady CA has a tree with n points numbered 1,2,...,n, and each edge has its weight. The unique route connecting two points is called a chain, and the length of a chain equals the sum value of the weights of the edges passed.
The point number m is called the root. Lady CA defines a special kind of chain called folded chain, the chain connecting the points numbered x,y(x≠y) is called a folded chain, if and only if the chain connecting the point numbered x and the root doesn't pass the point numbered y, and the chain connecting the point numbered y and the root doesn't pass the point numbered x.
Lady CA wants to find the length of the kth longest folded chain. Notice that the chain connecting the points numbered x,y and the chain connecting the points numbered y,x are the same.
Input
The first line contains an integer T(1≤T≤3)——The number of the test cases. For each test case:
The first line contains three integers n(2≤n≤50,000),m(1≤m≤n),k(1≤k≤n×(n−1)2). Between each two adjacent integers there is a white space separated.
The second line to the nth line describes the n−1 edges in the graph. Each line contains three integers u,v(1≤u,v≤n,u≠v),w(1≤w≤10,000), which means there is an edge which has a weight w connecting the points numbered u,v. Between each two adjacent integers there is a white space separated.
Output
For each test case, the only line contains the only integer that is the length of the kth longest folded chain. If the kth longest folded chain doesn't exist, print NO.
Sample Input
2
5 1 3
1 2 8
1 5 4
2 3 5
2 4 6
5 1 5
1 2 8
1 5 4
2 3 5
2 4 6
Sample Output
12
NO
