Farmer John каждый день добросовестно проверяет коров. Он проходит по некоторым из $M$ $(1 \le M \le 50,000)$ троп, пронумерованных $1,\ldots,M$, от пастбища $1$ до пастбища $N$ (для карт троп в тестовых данных такой путь всегда существует). На ферме Farmer John имеется $N$ $(1 \le N \le 10,000)$ пастбищ с номерами $1,\ldots,N$, сейчас соединённых двусторонними грунтовыми тропами. Каждая тропа $i$ соединяет пастбища $P1_{i}$ и $P2_{i}$ $(1 \le P1_i \le N; 1 \le P2_i \le N)$, а её прохождение занимает $T_{i}$ $(1 \le T_{i} \le 1,000,000)$ единиц времени.

Он хочет обновить некоторые тропы своей фермы, чтобы сэкономить время в долгом путешествии. А именно, он выберет $K$ $(1 \le K \le 20)$ троп и превратит их в шоссе, фактически сократив время прохождения каждой до $0$. Помогите FJ выбрать тропы для обновления, чтобы минимизировать время пути от пастбища $1$ до $N$.

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

• Строка 1: три целых числа, разделённых пробелами: $N$, $M$ и $K$.

• Строки $2,\ldots,M+1$: строка $i+1$ описывает тропу $i$ тремя целыми числами, разделёнными пробелами: $P1_{i}$, $P2_{i}$ и $T_{i}$.

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

• Строка 1: длина кратчайшего пути после обновления не более $K$ рёбер.

Примеры

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

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

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

1

Примечание

$K$ равно $1$; обновим тропу $3->4$, сократив время с $100$ до $0$. Новый кратчайший путь — $1->3->4$, теперь суммарное время равно $1$.

Автор задачи: Percy Liang, 2008