Телефонные линии
Фермер Джон хочет установить телефонную линию на своей ферме. К сожалению, телефонная компания отказывается сотрудничать, поэтому ему приходится платить за некоторые кабели, необходимые для подключения фермы к телефонной сети.
Имеются n заброшенных телефонных столбов, пронумерованных от 1 до n, которые разбросаны вокруг собственности фермера Джона; никакие кабели их не соединяют. Всего с помощью кабеля можно соединить p пар столбов; остальные находятся слишком далеко друг от друга.
i - ый кабель может соединить два разных столба a[i] и b[i] с длиной l[i] (1 ≤ l[i] ≤ 10^6), если будет использован. Никакая пара {a[i], b[i]} не встречается более одного раза. Столб 1 уже подключен к телефонной сети, а столб n находится на ферме. Столбы 1 и n должны быть соединены путем прокладки кабелей; остальные столбы могут использоваться или не использоваться.
Телефонная компания готова бесплатно предоставить фермеру Джону k кусков кабелей. Помимо этого, он должен будет заплатить цену, равную длине самого длинного кабеля среди тех которые ему еще будут нужны (каждая пара столбов соединяется отдельным кабелем), или 0 если ему не нужны дополнительные кабели.
Определите минимальную сумму, которую должен заплатить фермер Джон.
Входные данные
Первая строка содержит три целых числа n (1 ≤ n ≤ 1000), p (1 ≤ p ≤ 10000) и k (0 ≤ k < n). Каждая из следующих p строк содержит три целых числа a[i], b[i] и l[i].
Выходные данные
Выведите одно целое число - минимальную сумму, которую фермер Джон может заплатить. Если невозможно подключить ферму к телефонной сети, выведите -1.