Description

There is a binary apple tree where every node that branches must have exactly two children, meaning no node has only one child. The tree has a total of $N$ nodes, labeled from $1$ to $N$, and the root is always labeled $1$.

Each branch is described by the pair of node numbers it connects. Given that the tree has too many branches, some need to be pruned. However, some branches bear apples. Given the number of branches to retain, determine the maximum number of apples that can be preserved.

Input Format

The first line contains two integers $N$ and $Q$, where $N$ is the number of nodes in the tree, and $Q$ is the number of branches to retain.

The next $N-1$ lines describe the branches. Each line contains three integers: the first two are the node numbers connected by the branch, and the third is the number of apples on that branch.

Output Format

Output a single line with the maximum number of apples that can be preserved.

Sample 1

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

21

Constraints & Hints

For $100\%$ of the data, $1\le Q \le N \le 100, N\neq 1$, and the number of apples on each branch does not exceed $30000$.