Телефонні лінії
Фермер Джон хоче встановити телефонну лінію на своїй фермі. На жаль, телефонна компанія відмовляється співпрацювати, тому йому доводиться платити за деякі кабелі, необхідні для підключення ферми до телефонної мережі.
На території фермера Джона розкидані 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.