Батарея Бони
Батарея Бони
Бони исследует, какой электрический заряд батареи будет наиболее подходящим для транспортных средств школьного округа его мамы. Каждая школа имеет зарядную станцию. Поездка из одной школы в любую другую должна происходить с не более чем k подзарядками. Батарея автомобиля изначально имеет нулевой заряд и должна быть пополнена в начале каждой поездки; это считается одной из k подзарядок. Существует не более одной дороги между каждой парой школ, а также существует по крайней мере один путь, соединяющий каждую пару школ. Одной единицы заряда достаточно чтобы преодолеть одну единицу расстояния.
Зная расположение дорог и значение k, вычислить необходимый заряд электрической батареи транспортных средств.
Входные данные
Начинается с количества тестов t (1 ≤ t ≤ 50). Каждый тест начинается со строки, содержащей три целых числа n, k и m (2 ≤ n ≤ 100, 1 ≤ k ≤ 100), где n - количество школ, k - количество подзарядок, допустимых во время путешествия, m - количество дорог. Каждая из следующих m строк содержит три числа ui, vi и di (0 ≤ ui, vi < n, ui ≠ vi, 1 ≤ di ≤ 109) указывающих на то что дорога i соединяет школы ui и vi (0-индексируемые) двусторонней дорогой с расстоянием di.
Выходные данные
Для каждого теста вывести в отдельной строке наименьший возможный заряд электрической батареи.
2 4 2 4 0 1 100 1 2 200 2 3 300 3 0 400 10 2 15 0 1 113 1 2 314 2 3 271 3 4 141 4 0 173 5 7 235 7 9 979 9 6 402 6 8 431 8 5 462 0 5 411 1 6 855 2 7 921 3 8 355 4 9 113
300 688