Description

There is an apple tree. If a branch splits, it always splits into two (that is, there is no node with exactly one child).

The tree has $N$ nodes (leaves or branching points), numbered $1$ to $N$, and the root is always node $1$.

We describe a branch by the pair of node indices it connects. Below is a tree with $4$ branches:

2   5
 \ / 
  3   4
   \ /
    1

Now the tree has too many branches and needs pruning. However, some branches have apples on them.

Given the number of branches to keep, find the maximum number of apples that can be retained.

Input Format

The first line contains $2$ integers $N$ and $Q$, representing the number of nodes in the tree and the number of branches to keep, respectively.

Each of the next $N-1$ lines contains $3$ integers describing one branch: the first $2$ numbers are the indices of the nodes it connects, and the third number is the number of apples on that branch.

Output Format

Output a single integer, the maximum number of apples that can be retained.

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

21

Hint

$1 \leqslant Q < N \leqslant 100$, and the number of apples on each branch $\leqslant 3 \times 10^4$.

Translated by ChatGPT 5