Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

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 đủ.