403099: GYM101005 B Ktree

Memory Limit:64 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Ktreetime limit per test0.25 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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.

ExampleInput
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
Output
23

加入题单

上一题 下一题 算法标签: