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

Имеются n заброшенных телефонных столбов, пронумерованных от 1 до n, которые разбросаны вокруг собственности фермера Джона; никакие кабели их не соединяют. Всего с помощью кабеля можно соединить p пар столбов; остальные находятся слишком далеко друг от друга.

i - ый кабель может соединить два разных столба ai и bi с длиной li (1 ≤ li ≤ 106), если будет использован. Никакая пара {ai, bi} не встречается более одного раза. Столб 1 уже подключен к телефонной сети, а столб n находится на ферме. Столбы 1 и n должны быть соединены путем прокладки кабелей; остальные столбы могут использоваться или не использоваться.

Телефонная компания готова бесплатно предоставить фермеру Джону k кусков кабелей. Помимо этого, он должен будет заплатить цену, равную длине самого длинного кабеля среди тех которые ему еще будут нужны (каждая пара столбов соединяется отдельным кабелем), или 0 если ему не нужны дополнительные кабели.

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

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

Первая строка содержит три целых числа n (1 ≤ n ≤ 1000), p (1 ≤ p ≤ 10000) и k (0 ≤ k < n). Каждая из следующих p строк содержит три целых числа ai, bi и li.

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

Выведите одно целое число - минимальную сумму, которую фермер Джон может заплатить. Если невозможно подключить ферму к телефонной сети, выведите -1.