eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Авіаперельоти

Авіаперельоти

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Професору Форду необхідно потрапити на міжнародну конференцію. Він хоче витратити на дорогу найменшу кількість грошей, тому вирішив, що буде подорожувати виключно нічними авіарейсами (щоб не витрачатись на ночівлю в готелях), а вдень будт огялдати визначні місця тих міст, через які він буде проїзжати транзитом. Він уважно вивчив розклад авіаперельотів і обрав авіарейси, які підходять, вияснивши, що перельоти на обраних напрямках здійснюються кожної ночі і за одну ніч він не зможе здійснити два перельоти.

Тепер професор хоче знайти шлях найменшої вартості, враховуючи, що до конференції залтишись K ночей (тобто професор може здійснити не більше K перельотів).

Вхідні дані

У першому рядку знаходяться числа N (кількість міст), M (кількість авіарейсів), K (кількість ночей, що залишилось), S (номер міста, у якому живе професор), F (номер міста, у якому проводиться конференція). Обмеження: 2N100, 1M10^5, 1K100, 1SN, 1FN.

Далі йде M рядків, які задають розклад авіарейсів. i-й рядок містить три натуральних числа: S_i, F_i та P_i, де S_i - номер міста, з якого вилітає i-й рейс, F_i - номер міста, у яке прилітає i-й рейс, P_i - вартість перельоту i-м рейсом. 1S_iN, 1F_iN, 1P_i10^6.

Вихідні дані

Виведіть одне число - мінімальну вартість шляху, який підходить для професора. Якщо професор не зможе за K ночей дістатися до конференції, виведіть число -1.

Приклад

Вхідні дані #1
4 5 2 1 4
1 2 1
2 3 1
3 4 1
1 3 3
1 4 5
Вихідні дані #1
4