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