The problem description is the same as the problem DRAGON.

Input

The first line contains 3 integers N (1 ≤ N ≤ 3000), M (2 ≤ M ≤ N), K (1 ≤ K ≤ N), separated by single spaces. The N fruits are numbered 1..N, and the biggest fruit is always numbered 1. N-1 lines follow, each contains 3 integers i, j, k separated by spaces denoted that there is a branch between fruit i (1 ≤ i ≤ N) and fruit j (1 ≤ j ≤ N) and the weight of illness of this branch is k (0 ≤ k ≤ 100000).

Output

Output one line contains a single integer denoted the minimum weight of illness of the hydra. If we can't divide the fruit into M groups, output "-1" (without quotes).

Example

Input:
8 2 4
1 2 20
1 3 4 
1 4 13
2 5 10
2 6 12
3 7 15
3 8 5

Output:
4

Some new test cases were added.