Boni Batareyası
Boni, anasının məktəb dairəsi üçün nəqliyyat vasitələrinə hansı elektrik batareyasının daha uyğun olacağını araşdırır. Hər bir məktəbin bir doldurma stansiyası var. Bir məktəbdən digərinə səyahət ən çox k dəfə doldurulma ilə başa çatmalıdır. Avtomobilin batareyası əvvəlcə sıfır yüklə başlayır və hər səyahətin əvvəlində doldurulmalıdır; bu, k doldurulmalardan biri hesab olunur. Hər bir məktəb cütü arasında ən çox bir yol var və hər bir məktəb cütünü birləşdirən ən azı bir yol mövcuddur. Bir vahid yük bir vahid məsafəni qət etmək üçün kifayətdir.
Yolların yerləşməsini və k dəyərini bilmək, nəqliyyat vasitələrinin elektrik batareyası üçün lazım olan yükləməni hesablayın.
Giriş məlumatları
Testlərin sayı t (1 ≤ t ≤ 50) ilə başlayır. Hər bir test bir sıra ilə başlayır, üç tam ədəd n, k və m (2 ≤ n ≤ 100, 1 ≤ k ≤ 100) ehtiva edir, burada n - məktəblərin sayı, k - səyahət zamanı icazə verilən doldurulmaların sayı, m - yolların sayı. Növbəti m sətirdən hər biri üç ədəd u[i], v[i] və d[i] (0 ≤ u[i], v[i] < n, u[i] ≠ v[i], 1 ≤ d[i] ≤ 10^9) ehtiva edir, bu da i yolunun u[i] və v[i] məktəblərini (0-indeksli) iki tərəfli yolla d[i] məsafəsi ilə birləşdirdiyini göstərir.
Çıxış məlumatları
Hər bir test üçün ayrıca sətirdə mümkün olan ən kiçik elektrik batareyası yükləməsini çıxarın.
