题目描述

给定一棵有 $N$ 个顶点、$N-1$ 条边的带权树。边 $e$ 的权值 $w(e)$ 表示沿这条边画一次所消耗的粉笔量。

你需要用一支粉笔画完整棵树，使每条边至少被经过一次。

绘制过程中允许：

• 重复经过某条边；每经过一次，都会额外消耗 $w(e)$ 的粉笔；
• 最多抬起粉笔 $K$ 次。每次抬笔后，可以把粉笔无代价地移动到树上的任意顶点，再继续绘制。

最开始把粉笔放到树上的某个顶点不计作一次抬笔。

若边 $e$ 总共被经过 $t(e)\ge 1$ 次，则绘制总代价为

请计算最多抬笔 $K$ 次时的最小绘制代价。

输入格式

第一行包含两个整数 $N,K$。

接下来 $N-1$ 行，每行包含三个整数 $u,v,w$，表示顶点 $u,v$ 之间有一条权值为 $w$ 的无向边。

输出格式

输出一个整数，表示最小绘制代价。

数据范围

• $0\le K<N\le 2\cdot 10^5$；
• $1\le w(e)\le 10^6$；
• 输入保证构成一棵树。

子任务

样例一

输入

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

输出

40

样例一绘制方式

一种最优连续路线为

其中边 $(1,4)$ 和 $(4,5)$ 被重复经过。

样例二

输入

7 1
1 2 5
2 3 5
1 4 5
4 5 5
1 6 5
6 7 5

输出

30

样例二绘制方式

可以先画 $3\to2\to1\to4\to5$，抬笔并移动到顶点 $1$，再画 $1\to6\to7$。