Byteburg 是一个风景如画的小镇，拥有 $n$ 个交叉路口，由 $n-1$ 条双向街道连接。每个交叉路口都有一座漂亮的房子。Byteasar 著名的披萨店位于其中一个路口。Byteburg 的居民非常喜爱披萨，所以每天早上 Byteasar 会烘焙 $n-1$ 个披萨，并将它们送到全镇各地——除了他自己的房子外，每家一个。

由于没有人喜欢吃冷披萨，Byteasar 在他的车里安装了一个超现代的食物加热器。不幸的是，超现代意味着极其耗电，因此 Byteasar 希望尽量减少加热器开启的总时长。为此，他采取以下行动：他将几个披萨装进车里，打开加热器，然后将披萨送到选定的房子。当这一批次的最后一个披萨送达后，Byteasar 会关闭加热器并返回他的披萨店。由于他讨厌浪费时间，Byteasar 最多愿意进行 $k$ 次这样的配送行程。现在他想知道，在送完所有披萨的同时，加热器开启的最短总时长是多少。

Byteasar 在门口放下披萨并按门铃的停留时间可以忽略不计。

输入格式

输入的第一行包含两个正整数 $n$ 和 $k$，用空格隔开，分别表示 Byteburg 的交叉路口数量和 Byteasar 愿意进行的最大配送行程次数。交叉路口编号为 $1$ 到 $n$；披萨店作为镇上最重要的设施，位于 $1$ 号交叉路口。

接下来的 $n-1$ 行描述了街道网络：第 $i$ 行包含三个正整数 $a_i, b_i$ 和 $c_i$ ($a_i, b_i \le n, a_i \neq b_i$)，用空格隔开，表示有一条双向街道直接连接 $a_i$ 和 $b_i$ 号交叉路口，通行（双向）需要 $c_i$ 分钟。街道网络设计良好：从任何一个交叉路口都可以到达其他任何交叉路口，尽管可能是间接到达。

输出格式

输出仅一行，包含一个整数：Byteasar 为了让所有披萨都能热乎地送到，加热器必须开启的最短总时长（以分钟为单位）。

样例

样例输入 1

7 3
1 2 5
2 3 11
2 4 2
5 2 6
1 6 1
7 1 1

样例输出 1

34

说明

样例说明：Byteasar 将进行三次配送行程：$1 \to 2 \to 4 \to 2 \to 5 \to 1$（加热器开启的行驶时长为 15 分钟），$1 \to 2 \to 3 \to 1$（16 分钟），以及 $1 \to 6 \to 1 \to 7 \to 1$（3 分钟）。

数据范围

测试集由以下子任务组成。在每个子任务内，可能包含多个测试组。所有测试数据均满足：$n \ge 2, k \ge 1$ 且 $1 \le c_i \le 1\,000\,000$。