Формула-1
Формула-1
В тридесятом государстве есть n (1 ≤ n ≤ 800) городов, пронумерованных от 1 до n, и m (1 ≤ m ≤ 4000) двусторонних дорог между городами. Команда "Феррари" решила провести в тридесятом государстве тестовую сессию. Было решено провести k (1 ≤ k ≤ 40) заездов из первого города в n-ый, причём маршруты никаких двух заездов не должны в точности совпадать. При этом, если потребуется, в каких-то заездах разрешается несколько раз проехать по одной и той же дороге. Заезд заканчивается, как только гонщик приезжает в n-ый город (т.е. n-ый город не может быть промежуточным в маршруте заезда). В целях экономии бензина боссы "Феррари" требуют, чтобы суммарная длина маршрутов всех заездов была наименьшей. Вам необходимо найти эту длину.
Входные данные
Первая строка содержит числа k, n и m. Далее следуют m троек чисел, описывающих дороги - номера соединяемых дорогой городов и её длина (целое число от 1 до 9500).
Выходные данные
Выведите искомую суммарную длину. Гарантируется, что существует хотя бы один способ провести все заезды.
4 5 8 1 2 1 1 3 2 1 4 2 2 3 2 2 5 3 3 4 3 3 5 4 4 5 6
23