Recently Mr.Avantgarde has been assigned the task of delivering doughnuts .He borrowed an electric car for this task.There are N houses and each house has a charging station. There is at least one path of roads connecting each pair of houses. A trip from one house to any other must be completed using at most C rechargings. Car should always be recharged at the beginning of each trip(this counts as one of the C rechargings).As you know that Mr.Avantgarde is a lazy guy, Given the road network and C, compute the minimum range required of the electric car.

Note: With one recharging, the car can travel a distance equal to its range.

Input

Input begins with one integer T (0 < T< 6) denoting the number of test cases. Each test case begins with a line containing three integers N, C, and M (1 < N < 101, 0 < C < 101), where N and C are number of houses and number of rechargings. Next follow M lines each with three integers u, v and d (0 <= u,v < N, u != v,1 <= d <= 10^9) indicating that house u and v (0-indexed) are connected bidirectionally with distance d.

Output

For each test case, output minimum range required in each line.

Sample Input

2

4 2 4

0 1 100

1 2 200

2 3 300

3 0 400

10 2 15

0 1 113

1 2 314

2 3 271

3 4 141

4 0 173

5 7 235

7 9 979

9 6 402

6 8 431

8 5 462

0 5 411

1 6 855

2 7 921

3 8 355

4 9 113

Sample Output

300

688