eolymp
Competitions

April 17 Graphs contest

Bones`s Battery

Time limit 2 seconds
Memory limit 128 MiB

Bones is investigating what electric shuttle is appropriate for his mom's school district vehicle. Each school has a charging station. It is important that a trip from one school to any other be completed with no more than k rechargings. The car is initially at zero battery and must always be recharged at the start of each trip; this counts as one of the k rechargings. There is at most one road between each pair of schools, and there is at least one path of roads connecting each pair of schools.

Given the layout of these roads and k, compute the necessary range required of the electric shuttle.

Input data

Starts with a line with the number of test cases t (1t50). Each test case begins with a line containing three integers n, k and m (2n100, 1k100), where n denotes the number of schools, k denotes the maximum number of rechargings permitted per trip, and m denotes the number of roads. Next follow m lines each with three integers u[i], v[i] and d[i] (0u[i], v[i] < n, u[i]v[i], 1d[i]10^9) indicating that road i connects schools u[i] and v[i] (0-indexed) bidirectionally with distance d[i].

Output data

For each test case, output one line containing the minimum range required.

Examples

Input example #1
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 example #1
300
688
Source 2013 North America - Pacific Northwest Region Programming Contest, Problem B