作为绿色的使者，小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}$
