题目描述

有一棵点数为 $n$ 的树,树边带有边权。给定一个在 $0 \sim n$ 之内的非负整数 $k$,你要从中选择 $k$ 个点染成黑色,其余 $n-k$ 个点染成白色。染色完成后,你会获得一份收益:所有黑点两两之间的距离之和,加上所有白点两两之间的距离之和。

问收益的最大值是多少。

输入格式

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

第二到 $n$ 行每行三个正整数 $u, v, w$,表示树中存在一条长度为 $w$ 的边 $(u, v)$。输入保证所有点之间是连通的。

输出格式

输出一个整数,表示收益的最大值。

样例

3 1
1 2 1
1 3 2

3

提示

对于 $100\%$ 的数据,$0 \leq k \leq n \leq 2000$,$1 \leq w \leq 10^4$。