Tree

Problem Description

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.

Sample Input

1
5 2
1 2 5
2 3 2
2 4 3
2 5 4

Sample Output

14

Source

2020 Multi-University Training Contest 5