题目描述

一棵树有 $n$ 个点，编号为 $1 \sim n$ 。树边有长度。

现在要给其中 $m$ 个点打标记。

记打标记的点的集合为 $A$ ，未打标记的点的集合为 $B$ 。

记 $a$ 为 $A$ 集合内的任意两点的距离之和。

记 $b$ 为 $B$ 集合内的任意两点的距离之和。

记 $s$ 为 $a$ 与 $b$ 的和。

即：

$a = \sum_{i,j\in A,i<j}\operatorname{dist}(i,j)$

$b = \sum_{i,j\in B,i<j}\operatorname{dist}(i,j)$

$s=a+b$

其中 $dist(i,j)$ 表示点 $i$ 和点 $j$ 之间的距离，即两点之间的路径长度。

问：标记哪 $m$ 个点，可以使得 $s$ 的值最大？你只需要输出可以得到的 $s$ 最大值。

输入

第一行：包含两个整数 $n, m$ ；

接下来 $n-1$ 行：每行包含三个整数 $x,y,z$ 表示点 $x$ 和点 $y$ 之间有一条长度为 $z$ 的边。

一个整数，表示可以得到的 $s$ 的最大值。

3 2
1 2 3
3 2 1

$100\%$ 的数据：$n\leqslant 2000, 1\leqslant m, x, y\leqslant n, 0 \leqslant z \leqslant 10^9$