RXD and dividing

RXD has a tree $T$, with the size of $n$. Each edge has a cost.
Define $f(S)$ as the the cost of the minimal Steiner Tree of the set $S$ on tree $T$.
he wants to divide ${2, 3, 4, 5, 6, \dots n}$ into $k$ parts $S_1, S_2, S_3, \dots S_k$,
where $\bigcup S_i = \{2, 3, \dots , n \}$ and for all different $i, j$ , we can conclude that $S_i \bigcap S_j = \emptyset$.
Then he calulates $res = \sum_{i = 1}^{k}{f(\{1\}\bigcup S_i)}$.
He wants to maximize the $res$.
$1\leq k\leq n\leq 10^6$
$\text{the cost of each edge} \in [1, 10^5]$
$S_i$ might be empty.
$f(S)$ means that you need to choose a couple of edges on the tree to make all the points in $S$ connected, and you need to minimize the sum of the cost of these edges. $f(S)$ is equal to the minimal cost

There are several test cases, please keep reading until EOF.
For each test case, the first line consists of 2 integer $n, k$, which means the number of the tree nodes , and $k$ means the number of parts.
The next $n - 1$ lines consists of 2 integers, $a, b, c$, means a tree edge $(a, b)$ with cost $c$.
It is guaranteed that the edges would form a tree.
There are 4 big test cases and 50 small test cases.
small test case means $n \leq 100$.

For each test case, output an integer, which means the answer.

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

27

2017 Multi-University Training Contest - Team 3