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

Входные данные

Первая строка содержит числа k, n и m. Далее следуют m троек чисел, описывающих дороги - номера соединяемых дорогой городов и её длина (целое число от 1 до 9500).

Выходные данные

Выведите искомую суммарную длину. Гарантируется, что существует хотя бы один способ провести все заезды.