시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB133523032.609%

## 문제

The trick from problem “Alien” is a great way to improve a naive O(nk) dynamic programming to O(n log n). More problems with this trick can make the contest 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 ui and vi and has length li. Let dis(u, v) be the distance (sum of weights on simple path) between vertex u and vertex v in the tree.

Find k distinct vertices p1, p2, . . . , pk that maximize Σdis(pi, pi mod k+1). Output the maximum sum.

## 입력

The first line contains an integer T (1 ≤ T ≤ 105) indicating the number of test cases. For each test case:

The first line contains two integers n, k (2 ≤ n ≤ 2 · 105, 2 ≤ k ≤ n).

Each of the following n − 1 lines contains three integers ui, vi, li (1 ≤ ui, vi ≤ n, 1 ≤ li ≤ 106).

It is guaranteed that Σn ≤ 2 · 105.

## 출력

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

## 예제 입력 1

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


## 예제 출력 1

44