Cyclic Distance

The technique from the problem 'Alien' turns a naive O(nk) dynamic programming solution into O(n log n). More problems that use this technique would make contests better, like the two unsolved problems in 300iq Contest 2.

You are given a weighted tree with $n$ vertices and $n-1$ edges. The $i$-th edge connects vertices $u_i$ and $v_i$ and has length $l_i$. Let $dis(u, v)$ be the distance between vertices $u$ and $v$, which is the sum of the weights on the simple path between them.

Choose $k$ distinct vertices $p_1, p_2, \ldots, p_k$ that maximize $\sum dis(p_i, p_{(i \bmod k)+1})$. Output the maximum sum.

The first line contains an integer $T$ ($1 \le T \le 10^5$), the number of test cases. Each test case is given as follows.

The first line contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $2 \le k \le n$).

Each of the following $n-1$ lines contains three integers $u_i$, $v_i$, and $l_i$ ($1 \le u_i, v_i \le n$, $1 \le l_i \le 10^6$).

It is guaranteed that $\sum n \le 2 \cdot 10^5$.

For each test case, output one line containing one integer: the answer.