Батарея Бони
Бони исследует, какой электрический заряд батареи будет наиболее подходящим для транспортных средств школьного округа его мамы. Каждая школа имеет зарядную станцию. Поездка из одной школы в любую другую должна происходить с не более чем 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]
.
Выходные данные
Для каждого теста вывести в отдельной строке наименьший возможный заряд электрической батареи.