4227: 让傻瓜继续前进！(中等)

谢谢你帮助海蒂！现在是4月2日，但珍妮再次召唤她。恶作剧似乎没有结束。。。


与此同时，海蒂决定不再信任她的朋友。
无论如何，不要太多。她相对缺乏信任的表现如下：以前她不会被要求两次访问同一个人，现在她只能确定她不会被允许访问同一人超过k次。
（以珍妮为例，这包括她一开始的第一次访问。简单版本中的情况对应于设置k = 1.)


这并没有看起来那么糟糕，因为两个朋友之间的一张单程票就可以让海蒂在这对朋友之间一整天（双向）旅行。
换句话说，一旦她支付了一对朋友之间的旅行费用，这对朋友之间所有的进一步旅行都是免费的。


在最坏的情况下，海蒂现在会浪费多少钱？

第一行包含两个空格分隔的整数–好友数n(3<=n<=10⁵)和参数k(1<=k<=10⁵).
接下来n - 1行每行包含三个空格分隔的整数u、v和c（0 ≤ u,v ≤ n - 1, 1 ≤ c ≤ 10⁴），
这意味着u和v是朋友并且他们之间旅游的花费是c。


再次保证输入的社交网络形成树。

同样，输出一个整数——门票成本的最大总和。

9 3
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3

15

样例输入

9 5
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3

样例输出 

17

样例输入

11 6
1 0 7932
2 1 1952
3 2 2227
4 0 9112
5 4 6067
6 0 6786
7 6 3883
8 4 7137
9 1 2796
10 5 6200
样例输出 
54092