作为绿色的使者，小h有棵$n$个节点的带权树。

找出$k$个点$A_1,A_2,\cdots,A_k$。

使得$\sum_{i=1}^{k-1}dis(A_i,A_{i+1})$最小。

其中$dis(i,j)$表示点$i$到点$j$的树上最短路。

输入格式

第一行两个正整数$n,k$,表示树的顶点数和需要选出的点个数。

接下来$n-1$行每行$3$个非负整数$x,y,z$,表示从存在一条从$x$到$y$权值为$z$的边。

$1 \leq k \leq n$。

$1 \leq x,y \leq n$。

$1 \leq z \leq 10^5$。

输出格式

一行一个整数,表示最小的距离和。

样例一

input

5 4
1 2 1
2 3 3
2 4 2
4 5 5

output

7

数据范围

对于$10\%$的数据,$\ \ n \leq 10$。

对于另外$10\%$的数据,$\ k=n$。

对于另外$20\%$的数据,$\ n \leq 50$。

对于另外$20\%$的数据,$\ n \leq 200$。

对于$100\%$的数据,$\ \ n \leq 3000$。

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载