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
Output:
300
688