Торговая сеть открыла n магазинов, пронумерованных от 1 до n. Между некоторыми парами магазинов организованы маршруты доставки. Каждый маршрут соединяет два магазина и имеет стоимость проезда.

У вас есть k купонов для бесплатного проезда. Один купон можно использовать на одном маршруте, и тогда стоимость проезда по этому маршруту считается равной 0.

Требуется определить минимальную суммарную стоимость, за которую можно добраться из магазина 1 в магазин n, если разрешено использовать не более k купонов.

Каждый маршрут можно сделать бесплатным не более одного раза при прохождении по нему.

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

В первой строке заданы три целых числа n, m, k — количество магазинов, количество маршрутов и количество купонов.

В следующих m строках содержатся описания маршрутов. Каждая строка содержит три целых числа u, v, w, где u и v — номера магазинов, соединённых маршрутом, а w — стоимость проезда по нему.

Все данные подаются через стандартный ввод.

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

Выведите одно целое число — минимальную стоимость пути из магазина 1 в магазин n.

Если добраться невозможно, выведите -1.

Результат следует вывести в стандартный вывод.

Ограничения

• 2 <= n <= 100000
• 0 <= m <= 300000
• 0 <= k <= 50
• 1 <= u, v <= n
• 0 <= w <= 1000000

Примеры

Пример 1

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

2 1 0
1 2 7

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

7

Пример 2

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

3 2 1
1 2 5
2 3 9

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

5