순환 거리

'Alien' 문제에 나온 기법은 단순한 O(nk) 동적 계획법을 O(n log n)으로 바꾸는 좋은 방법이다. 이 기법을 쓰는 문제가 더 많아지면 대회가 더 나아질 수 있다. 300iq Contest 2에 남은 미해결 문제 두 개가 그런 예다.

가중치가 있는 트리가 주어진다. 정점은 $n$개, 간선은 $n-1$개다. $i$번째 간선은 정점 $u_i$와 $v_i$를 잇고, 길이는 $l_i$이다. $dis(u, v)$를 정점 $u$와 $v$ 사이 단순 경로에 있는 간선 가중치의 합이라고 하자.

서로 다른 정점 $k$개 $p_1, p_2, \ldots, p_k$를 골라 $\sum 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$이 보장된다.

각 테스트 케이스마다 답을 나타내는 정수 하나를 한 줄에 출력한다.