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.
Input
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\leq n\leq 2 \times 10^{5},0\leq 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\leq u,v\leq n,0\leq d \leq 10^{9})$.
You may assume that $\sum n \leq 10^{6}$.
Output
For each test case, output one line containing a single integer $ans$ denoting the total weight of the subgraph.