CLZDOUGH  Avantgarde and Doughnut
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 (0indexed) 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
hide comments
mahmud2690:
20161005 19:51:31
in the second case how to go node (6) to node(7) using 688 range? 

:D:
20161003 20:34:16
Really interesting take on "shortest path" problem type. Also seems to be pretty optimization friendly. 
Added by:  CSI 
Date:  20141015 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 