Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0061 - BONES’S BATTERY

   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

   Input begins with a line with one integer T (1 ≤ T ≤ 50) denoting the number of test cases. Each test case begins with a line containing three integers N , K, and M (2 ≤ N ≤ 100, 1 ≤ K ≤ 100), 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 ui, vi, and di (0 ≤ ui, vi < N , uivi, 1 ≤ di 109) indicating that road i connects schools ui and vi (0-indexed) bidirectionally with distance di.

Output

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

Examples

stdin

stdout

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

300

688


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-01-03
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.NA Pacific NW 2013.B

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.