题目描述

经过 $100$ 年的努力，$C$ 国终于出现了短暂的和平。但这种和平是暂时的，因为 $C$ 国仍然是军阀割据的局面。

$C$国一共有 $n$ 个城市，有 $n-1$ 个长度不一的虫洞将它们联系起来。每个军阀都控制着一个城市。

首都是 $1$ 号城市。

两座城市的距离定义为，从一座城市穿越到另一座城市所经过的虫洞长度之和。

为了提高信息传输的效率，军阀们决定合并。

每次，他们可以选择与其有虫洞相接的两个城市结盟，并且每个联盟不能拥有超过 $k$ 个军阀。

一座城市只能结一个盟。

结盟后，信息在联盟内传递将不用花任何时间，在联盟间传递所需的时间为经过虫洞的长度。

试求出信息从首都传到每个城市的最小时间之和。

请注意，方案可能独立，不要求在同一种方案内。

输入格式

第一行两个正整数 $n,k$。

接下来 $n-1$ 行，每行三个正整数 $u,v,w$，表示 $u,v$ 两座城市有长度为 $w$ 的虫洞连接。

输出格式

输出一行一个整数，表示信息从首都传到所有城市的最小时间之和。

样例输入 1

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

样例输出 1

13

样例解释

这是样例的图。显然 $1,2,3,4,5,10,11$ 都不需要时间，直接与 $1$ 结盟就可以做到 $0$ 时间内传达。

以 $6$ 为例，它可以结盟成为 $6,4,3$，这样信息传输只会通过 $1→3$ 的边，时间为 $3$，可以证明这是最优方案。

$6,7,8,9$ 四个点最小用时分别为 $3,4,4,2$，总时间为 $13$。

数据范围 下表数据表示最大值。

Subtask	n	k	特殊性质	分值
1	$10^5$	10	无	10
2		1
3	$10^4$		保证数据是一条链	20
4	$10^5$		无	60

对于$100\%$ 的数据，$1≤k≤n≤10^5,1≤w≤10^9$。