Boninin Batareyası#6962
Boni, anasının işlədiyi rayondakı məktəb avtobusları üçün ən uyğun batareya həcminin nə olacağını araşdırır. Hər məktəbin özünə məxsus bir doldurma stansiyası var. Bir məktəbdən digərinə edilən hər hansı bir gəzinti ən çox dolumu ilə həyata keçirilməlidir. Batareya öncədən boşdur və hər səyahətə başlamadan əvvəl tam doldurulmalıdır; bu başlanğıc dolumu dolumların sayına daxil edilir.
Hər bir məktəb cütü arasında ən çox bir yol mövcuddur, və yol qrafiki əlaqəlidir, yəni hər iki məktəb arasında heç olmasa bir yol mövcuddur. Bir vahid məsafəni qət etmək üçün bir vahid doldurma tələb olunur.
Yolların yerləşməsini və dəyərini bildikdə, məktəb avtobusları üçün minimum tələb olunan batareya dolumunu müəyyən edin.
Birinci sətr testlərin sayı t~(1 \le t \leq 50).
Hər bir test üç tam ədəd , və m~(2 \le n \le 100, 1 \le k \le 100) ilə başlayan bir sətrdən ibarətdir, burada:
— məktəblərin sayı,
— gəzinti zamanı icazə verilən maksimum dolum sayı,
— yolların sayı.
Sonra sətr gəlir, hər biri üç ədəd u_i, v_i və d_i~(0 \le u_i, v_i < n, u_i \ne v_i, 1 \le d_i \le 10^9) ehtiva edir.
Bu məlumatlar yol -nin məktəbləri u_i və v_i (məktəblər sıfırdan başlayaraq nömrələnir) iki tərəfli bir yolla uzunluğu d_i ilə birləşdirdiyini təsvir edir.
Hər bir test üçün ayrı-ayrı sətirdə minimum tələb olunan batareya dolumunu çap edin.
Nümunə 1