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.