Description

给出一颗树，根结点编号为$1$。有一名医护人员从根出发，沿着树边移动，去每个叶子采集信息，最后返回根。他的采集顺序是固定的，每当走到一个结点$u$，他会先走向编号最小的孩子，并访问完其中所有的家庭并回到$u$，然后再走向编号第二小的孩子，依此直到访问完$u$子树中所有的家庭返回上一层。可以发现访问叶子的顺序也正好是家庭住址列表上的顺序。

沿着树边移动需要一定时间，为了节约时间，可以将家庭列表分成连续的$k$段，并让$k$个医护人员同时从根出发，每人访问一个区间中的家庭然后返回。请你计算出统计完所有家庭的体温所需要的最短时间。

Input Format

第一行两个整数$n, k$，分别表示树中的结点数和医护人员数。

接下来$n-1$行，每行三个整数$u, v, w$，表示一条从$u$到$v$，经过花费时间$w$的边。

Output Format

一行一个整数，表示统计完所有家庭的最短时间。

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

对 $30\%$ 的数据，$1 \le n \le 20$

对另外 $10 \%$ 的数据，$k = 1$

对另外 $20 \%$ 的数据，$k = 2$

对 $100\%$ 的数据，$1 \le n \le 2*10^5, 1 \le k \le m, 1 \le u, v \le n, 0 \le w \le 10^9$，$m$为叶子数。

样例说明

图示见题目背景。

第一个人的路径为RT->Z1->Z2->RT，耗时66。

第二个人的路径为RT->Z3->Z4->RT，耗时32。

让一个人访问Z2，另一个人访问Z1、Z3、Z4的方案是不合法的。