Farmer John хочет провести телефонную линию на ферму. К сожалению, телефонная компания не желает сотрудничать, поэтому ему придётся оплатить часть кабелей, необходимых для подключения фермы к телефонной сети.

По его участку разбросаны $N$ одиноких телефонных столбов, $(1 \le N \le 1,000)$, удобно пронумерованных $1..N$; никаких кабелей между ними нет. Всего $P$ пар столбов, $(1 \le P \le 10,000)$, можно соединить кабелем; остальные находятся слишком далеко друг от друга.

Кабель с номером $i$ может соединить два различных столба $A_i$ и $B_i$, а его длина при использовании составляет $L_i$ единиц, $(1 \le L_i \le 1,000,000)$. Входные данные никогда не задают одну пару {$A_i,B_i$} более одного раза. Столб $1$ уже подключён к телефонной сети, а столб $N$ находится на ферме. Столбы $1$ и $N$ нужно соединить путём из кабелей; остальные столбы можно использовать или не использовать.

Как выяснилось, телефонная компания готова бесплатно предоставить Farmer John $K$ кабелей, $(0 \le K < N)$. За остальные он заплатит сумму, равную длине самого длинного из оставшихся необходимых кабелей (каждая пара столбов соединяется отдельным кабелем), либо $0$, если дополнительных кабелей не требуется.

Определите минимальную сумму, которую должен заплатить Farmer John.

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

Читайте входные данные из стандартного ввода.

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

• Строки $2..P+1$: строка $i+1$ содержит три целых числа, разделённых пробелами: $A_i$, $B_i$ и $L_i$.

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

Запишите ответ в стандартный вывод.

• Строка 1: одно целое число — минимальная сумма, которую может заплатить Farmer John. Если подключить ферму к телефонной компании невозможно, выведите $-1$.

Примеры

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

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

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

4

Примечание

Есть 5 столбов. Столб $1$ нельзя напрямую соединить со столбами $4$ или $5$. Столб $5$ нельзя напрямую соединить со столбами $1$ или $3$. Все остальные пары можно соединить. Компания предоставит один бесплатный кабель.

Если соединить столб $1$ со столбом $3$, столб $3$ со столбом $2$, а столб $2$ со столбом $5$, Farmer John понадобятся кабели длины $4$, $3$ и $9$. Компания предоставит кабель длины $9$, поэтому самый длинный из оставшихся необходимых кабелей имеет длину $4$.

Автор задачи: Paul Christiano, 2007