Aphelios likes to play with tree. A weighted tree is an undirected connected graph without cycles and each edge has a weight. The degree of each vertex is the number of vertexes which connect with it. Now Aphelios has a weighted tree T with n vertex and an integer k, and now he wants to find a subgraph G of the tree, which satisfies the following conditions:
1. G should be a connected graph, in other words, each vertex can reach any other vertex in the subgraph G.
2. the number of the vertex whose degree is larger than k is no more than 1.
3. the total weight of the subgraph is as large as possiblie.
Now output the maximum total weight of the subgraph you can find.
输入格式
The first line contains an integer q, which represents the number of test cases.
For each test case, the first line contains two integer n and k(1≤n≤2×105,0≤k<n).
For next n−1 lines , each line contains 3 numbers u,v,d, which means that there is an edge between u and v weighted d(1≤u,v≤n,0≤d≤109).
You may assume that ∑n≤106.
输出格式
For each test case, output one line containing a single integer ans denoting the total weight of the subgraph.