RXD and dividing

Problem Description

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

Input

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$.

Output

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

Sample Input

5 4

1 2 3

2 3 4

2 4 5

2 5 6

Sample Output

27

Source

2017 Multi-University Training Contest - Team 3

https://acm.hdu.edu.cn/showproblem.php?pid=6060