样例下载

问题描述

一棵树含有 N 个节点，编号为 1 ~ N，其中 1 号为根节点。对于任意一个节点，它要么没有儿子节点，要么恰好有两个儿子节点。每条树边有一个长度。

现在你要对这棵树进行剪枝。你准备使得这棵树最后恰好保留 M 条树边。当然，你不能在剪枝的时候把根节点剪掉，即你必须保证剩下这棵树的根节点仍然是 1 号节点。

你希望使得剩余 M 条树边的长度之和尽可能大。

请你输出这个最大值。

输入格式

第一行：两个整数 N, M

接下来 N-1 行：每行三个整数 u, v, w, 表示节点 u 和 v 之间有一条长度为 w 的边。

输出格式

一个整数，表示答案。

输入样例

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

输出样例

7

样例解释

数据范围

1 ≤ M < N ≤ 100, 1 ≤ u, v ≤ N, 0 ≤ w ≤ 10^9。