Батарея Боні#6962

Батарея Боні

2 секунди

128 мегабайтів

Дуже легка

Боні досліджує, який обсяг заряду акумулятора буде найбільш підходящим для шкільних автобусів округу, де працює його мама. Кожна школа має власну зарядну станцію. Будь-яка поїздка з однієї школи в іншу має виконуватися з не більше ніж $k$ підзарядками. Акумулятор спочатку порожній і має бути повністю заряджений перед початком кожної поїздки; це початкове заряджання також враховується в числі $k$ підзарядок.

Між кожною парою шкіл існує не більше однієї дороги, при цьому граф доріг зв'язний, тобто завжди існує хоча б один шлях між будь-якими двома школами. Для подолання однієї одиниці відстані потрібна одна одиниця заряду.

Знаючи розташування доріг і значення $k$ , визначте мінімально необхідний заряд акумулятора для шкільних автобусів.

Вхідні дані

Перший рядок містить число тестів $t (1 \leq t \leq 50)$ t~(1 \le t \leq 50).

Кожен тест починається рядком з трьома цілими числами $n$ , $k$ і $m (2 \leq n \leq 100, 1 \leq k \leq 100)$ m~(2 \le n \le 100, 1 \le k \le 100), де:

$n$ — кількість шкіл,
$k$ — максимально допустима кількість підзарядок під час поїздки,
$m$ — кількість доріг.

Далі слідують $m$ рядків, кожен з яких містить три числа $u_{i}, v_{i}$ u_i, v_i і $d_{i} (0 \leq u_{i}, v_{i} < n, u_{i} \neq = v_{i}, 1 \leq d_{i} \leq 1 0^{9})$ d_i~(0 \le u_i, v_i < n, u_i \ne v_i, 1 \le d_i \le 10^9).

Ці дані описують, що дорога $i$ з'єднує школи $u_{i}$ u_i та $v_{i}$ v_i (школи нумеруються з нуля) двостороннім шляхом довжиною $d_{i}$ d_i.

Вихідні дані

Для кожного тесту в окремому рядку виведіть мінімально необхідний заряд акумулятора.

Приклади

Приклад 1