Телефонні лінії

Фермер Джон хоче провести телефонну лінію на свою ферму. На жаль, телефонна компанія не надто охоче йому допомагає, тому йому доведеться оплатити частину кабелів, необхідних для підключення ферми до телефонної мережі.

На території фермера Джона розкидано $n$ самотніх телефонних стовпів, пронумерованих від $1$ до $n$. Наразі жоден з них не з'єднаний кабелем з іншим. Всього існує $p$ пар стовпів, які можна з'єднати кабелем; інші пари знаходяться занадто далеко один від одного.

$i$-й кабель може з'єднати два різні стовпи a_i та b_i і має довжину l_i~(1 \le l_i \le 10^6) одиниць. Кожна пара {a_i,b_i} зустрічається у вхідних даних не більше одного разу.

Стовп $1$ вже підключений до телефонної мережі, а стовп $n$ знаходиться на фермі. Стовпи $1$ та $n$ необхідно з'єднати шляхом, що складається з кабелів; інші стовпи можуть використовуватися або не використовуватися.

Телефонна компанія готова безкоштовно надати фермеру Джону $k$ відрізків кабелю. За кожен кабель понад ці $k$ безкоштовних кабелів фермер повинен заплатити суму, що дорівнює довжині найдовшого з решти необхідних йому кабелів, або $0$, якщо додаткові кабелі йому не потрібні.

Визначте мінімальну суму, яку повинен заплатити фермер Джон.