题目背景

在疫情扩散后，疾控中心的医护人员对来自武汉的人员进行了家庭访问，对体温进行测量。医护人员从疾控中心出发，按照一定顺序对所有家庭进行访问，然后汇总数据。

家庭列表上记录着类似于A街道B小区C号楼D户一样的住址，按照字典顺序排列，因此每个区域中的家庭在列表中总是相邻的。医护人员在访问完某个区域（比如B1小区）的所有家庭后，需要将数据送至上一层（比如A街道）的管理机构中，然后继续访问（比如B2小区）中的家庭。

也就是说，医护人员的移动路径类似一颗树，其中树根代表疾控中心，树叶代表家庭，而中间的结点代表一层一层的管理区域。结点的孩子代表下一层的区域（或者家庭），是有序的。从根到某个家庭的路径上所有的点正好组成了这个家庭的地址。

如图，4家的地址分别为（按顺序）

• A1-B1-C1-Z1
• A1-B1-C1-Z2
• A1-B1-Z3
• A2-B2-C3-Z4

箭头仅代表归属关系，所有路均可双向通行。

本质上，题目给出的树就是住址构成的 字典树/Trie树 。

题目描述

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

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

输入格式

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

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

输出格式

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

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

提示

对 $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的方案是不合法的。