Description

本杰明眼中的花形态奇特，这种花有 $n$ 个节点，节点标号 $1 ~ n$，节点初始均为红色，本杰明被赋予了某种权能，他能够将 $k$ 个节点变为白色节点，任一红色节点与任一白色节点会共鸣从而产生舒适度，其值为两点间距离的大小，试问产生的舒适度之和最大会是多少？

Format

Input

第一行包含两个整数 $n,k(1 \leq k \leq n \leq 2000 )$接下来 $n - 1$ 行每行三个正整数 $u, v, w(1 \leq u, v \leq n, 1 \leq w \leq 2000)$，表示节点 $u$ 和节点 $v$ 之间有一条长度为 $w$ 的边，题目保证 $n$ 个节点联通

Output

输出一个整数，表示舒适度之和的最大值

Samples

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

24

3 2
1 2 2
1 3 1

5

Hint

对于样例 $1$：一种取得最大值的方法是：将点 $1,2,4$ 染成白色对于样例 $2$：一种取得最大值的方法是：将点 $1,3$ 染成白色