Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P146PROJ - ROUND 6J - Xe đạp điện

Tí mới được bố mẹ mua cho chiếc xe đạp điện. Nhân cơ hội này, Tí muốn đi tham quan tất cả các trường đại học ở Hà Nội. Ở mỗi trường đại học đều có trạm sạc free dành cho xe đạp điện. Tí muốn di chuyển giữa 2 ngôi trường bất kì với không quá K lần sạc ắc quy. Sạc điện cho xe mất khá nhiều thời gian, quãng thời gian đó quá đủ để Tí đi tham quan xong trường đại học đang dừng chân. Vì vậy, để tiết kiệm thời gian, Tí sạc trong thời gian vừa đủ và thời gian mỗi lần sạc tại các trạm là như nhau. Trung bình cứ sạc được 1 phút thì sẽ đi được 1 km.

Ban đầu, xe hết điện và Tí phải sạc tại địa điểm xuất phát (tính là 1 lần sạc). Các bạn hãy tính giúp Tí xem mỗi lần sạc, Tí phải sạc ít nhất bao lâu để có thể đáp ứng được hành trình của mình?

Input

Dòng đầu tiên là số lượng bộ test T (1 <= T <= 50).

Mỗi bộ test gồm dòng đầu tiên là 3 số nguyên N, K và M  (2 <= N <= 100, 1 <= K <= 100), trong đó N là số trường đại học, K là số lần sạc tối đa cho mỗi chuyến đi, và M là số tuyến đường.

M dòng tiếp theo, mỗi dòng gồm 3 số nguyên u_i, v_i, d_i (0 <= u_i; v_i < N, u_i = v_i, 1 <= d_i <= 10^9) thể hiện tuyến đường i nối trường học u_i và v_i, và có độ dài là d_i.

Output

Với mỗi test, in ra một số nguyên duy nhất là thời gian sạc ít nhất cho mỗi lần sạc của xe là bao nhiêu, để có thể di chuyển giữa 2 ngôi trường bất kì với không quá K lần sạc?

Example

Input:
2
4 2 4
0 1 10
1 2 20
2 3 30
3 0 40
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:

30 688

Giải thích test 1:

Độ dài đường đi ngắn nhất giữa các cặp địa điểm là:

0 – 1: 10 km
0 – 2: 30 km
0 – 3: 40 km
1 – 2: 20 km
1 – 3: 50 km
2 – 3: 30 km

Để đi được từ trường 2 tới trường 3, cần sạc ắc quy ít nhất 30 phút để xe có thể đi được 30 km.
Nếu mỗi lần sạc 30 phút, đi từ trường 0 tới trường 3, sẽ đi theo đường 0--> 1 --> 2 --> 3, tổng
quãng đường là 60 km, cần 2 lần sạc, lần 1 sạc tại trường 0 và lần thứ hai tại trường 2.
Như vậy, mỗi lần cần sạc 30 phút là vừa đủ.


Được gửi lên bởi:adm
Ngày:2014-03-11
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

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