Телефонные линии
Телефонные линии
Фермер Джон хочет установить телефонную линию на своей ферме. К сожалению, телефонная компания отказывается сотрудничать, поэтому ему приходится платить за некоторые кабели, необходимые для подключения фермы к телефонной сети.
Имеются 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.
5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6
4