403099: GYM101005 B Ktree

You are given a tree consisting of N nodes and N - 1 weighted edges. You want to remove exactly M edges so that node 1 will remain in a component with exactly K nodes, while minimizing the sum of costs of the removed edges.

The first line of input will contain three positive integers N(1 ≤ N < 75), M(1 ≤ M < N) and K(1 ≤ K ≤ N). The following N - 1 lines will each contain 3 numbers x y c, describing an edge between nodes x and y of cost c.

The first and only line of your output should contain one integer representing the minimum cost required, or  - 1 if there is no valid solution.

10 4 3
1 2 10
1 3 21
1 4 4
2 7 2
3 5 5
3 6 12
6 8 7
6 9 6
6 10 3

23