来自“Alien”问题的技巧是将朴素的 $O(nk)$ 动态规划优化到 $O(n \log n)$ 的绝佳方法。 更多使用此技巧的问题可以使比赛变得更好，就像 300iq Contest 2 中那两道未解决的问题一样。

给定一棵包含 $n$ 个顶点和 $n - 1$ 条边的带权树。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，长度为 $l_i$。令 $\text{dis}(u, v)$ 为树中顶点 $u$ 和顶点 $v$ 之间的距离（简单路径上权值之和）。

寻找 $k$ 个不同的顶点 $p_1, p_2, \dots, p_k$，使得 $\sum_{i=1}^{k} \text{dis}(p_i, p_{i \bmod k + 1})$ 最大化。输出该最大和。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。对于每个测试用例： 第一行包含两个整数 $n, k$ ($2 \le n \le 2 \cdot 10^5, 2 \le k \le n$)。 接下来的 $n - 1$ 行，每行包含三个整数 $u_i, v_i, l_i$ ($1 \le u_i, v_i \le n, 1 \le l_i \le 10^6$)。 保证 $\sum n \le 2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数：即答案。

样例

输入 1

1
5 3
1 2 4
1 3 1
1 4 8
4 5 9

输出 1

44