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

Вхідні дані

Перший рядок містить три числа k, n та m. Далі йдуть m трійок чисел, які описують дороги - номери з'єднуваних дорогою міст та її довжина (ціле число від 1 до 9500).

Вихідні дані

Виведіть шукану сумарну довжину. Гарантується, що існує хоча б один спосіб провести всі заїзди.