Батарея Боні
Боні досліджує, який електричний заряд батареї буде найбільш підходящим для транспортних засобів у шкільному окрузі його мами. Кожна школа має зарядну станцію. Поїздка з однієї школи до будь-якої іншої повинна відбуватися з не більше ніж k підзарядками. Батарея автомобіля спочатку має нульовий заряд і повинна бути поповнена на початку кожної поїздки; це вважається однією з k підзарядок. Існує не більше однієї дороги між кожною парою шкіл, а також існує принаймні один шлях, що з'єднує кожну пару шкіл. Однієї одиниці заряду достатньо, щоб подолати одну одиницю відстані.
Знаючи розташування доріг і значення k, обчисліть необхідний заряд електричної батареї транспортних засобів.
Вхідні дані
Починається з кількості тестів t (1 ≤ t ≤ 50). Кожен тест починається з рядка, що містить три цілі числа n, k і m (2 ≤ n ≤ 100, 1 ≤ k ≤ 100), де n - кількість шкіл, k - кількість підзарядок, допустимих під час подорожі, m - кількість доріг. Кожен з наступних m рядків містить три числа u[i], v[i] і d[i] (0 ≤ u[i], v[i] < n, u[i] ≠ v[i], 1 ≤ d[i] ≤ 10^9), що вказують на те, що дорога i з'єднує школи u[i] і v[i] (0-індексовані) двосторонньою дорогою з відстанню d[i].
Вихідні дані
Для кожного тесту виведіть в окремому рядку найменший можливий заряд електричної батареї.