Description

Given a tree whose root node is numbered $1$. A medical worker starts from the root, moves along the edges, collects information from every leaf, and finally returns to the root. The visiting order is fixed: whenever he reaches a node $u$, he first goes to the child with the smallest index, visits all households in that child subtree and comes back to $u$, then goes to the child with the second smallest index, and so on, until all households in the subtree of $u$ have been visited and he returns to the parent. It can be seen that the order of visiting leaves is exactly the order in the household address list.

Moving along an edge takes time. To save time, we may split the household list into $k$ continuous segments, and let $k$ medical workers start from the root at the same time. Each worker visits the households in one segment and then returns. Please compute the minimum time needed to finish collecting temperatures for all households.

Input Format

The first line contains two integers $n, k$, representing the number of nodes in the tree and the number of medical workers.

The next $n-1$ lines each contain three integers $u, v, w$, representing an edge between $u$ and $v$, with travel time cost $w$.

Output Format

Output one integer in one line, representing the minimum time needed to finish the temperature survey for all households.

11 2
1 2 2
1 3 3
2 4 1
3 5 2
4 6 2
4 7 3
5 8 1
6 9 3
6 10 25
8 11 4

66

Hint

For $30\%$ of the testdata, $1 \le n \le 20$.

For another $10\%$ of the testdata, $k = 1$.

For another $20\%$ of the testdata, $k = 2$.

For $100\%$ of the testdata, $1 \le n \le 2*10^5$, $1 \le k \le m$, $1 \le u, v \le n$, $0 \le w \le 10^9$, where $m$ is the number of leaves.

Sample Explanation

See the figure in the Background.

The first person’s route is RT->Z1->Z2->RT, costing 66.

The second person’s route is RT->Z3->Z4->RT, costing 32.

The plan where one person visits Z2 and the other visits Z1, Z3, Z4 is invalid.

Translated by ChatGPT 5