9. 二叉苹果树

【题目描述】

有一棵苹果树，如果树枝有分叉，一定是分 $2$ 叉（即没有只有 $1$ 个儿子的结点）。

这棵树共有 $N$ 个结点（叶子点或者树枝分叉点），编号为 $1 \sim N$，树根编号一定是 $1$。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一棵有 $4$ 个树枝的树：

2  5
\ /
 3   4
  \ /
   1

现在这棵树枝条太多了，需要剪枝，但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

【输入格式】

第 $1$ 行 $2$ 个正整数，$N$ 和 $Q(1 \leq Q \leq N，1 \leq N \leq 100)$。

$N$ 表示树的结点数，$Q$ 表示要保留的树枝数量。 

接下来 $N-1$ 行描述树枝的信息：

每行 $3$ 个整数 $u,v,w$，表示树枝 $(u,v)$ 上有 $w（w \leq 30000）$ 个苹果。

【输出格式】

输出一个数，表示最多能留住的苹果数量。

【样例输入】

5 2
1 3 1
1 4 10
2 3 20
3 5 20

【样例输出】

21