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.