Авіаперельоти
Професору Форду необхідно потрапити на міжнародну конференцію. Він хоче витратити на дорогу найменшу кількість грошей, тому вирішив, що буде подорожувати виключно нічними авіарейсами (щоб не витрачатись на ночівлю в готелях), а вдень будт огялдати визначні місця тих міст, через які він буде проїзжати транзитом. Він уважно вивчив розклад авіаперельотів і обрав авіарейси, які підходять, вияснивши, що перельоти на обраних напрямках здійснюються кожної ночі і за одну ніч він не зможе здійснити два перельоти.
Тепер професор хоче знайти шлях найменшої вартості, враховуючи, що до конференції залтишись K ночей (тобто професор може здійснити не більше K перельотів).
Вхідні дані
У першому рядку знаходяться числа N (кількість міст), M (кількість авіарейсів), K (кількість ночей, що залишилось), S (номер міста, у якому живе професор), F (номер міста, у якому проводиться конференція). Обмеження: 2 ≤ N ≤ 100, 1 ≤ M ≤ 10^5, 1 ≤ K ≤ 100, 1 ≤ S ≤ N, 1 ≤ F ≤ N.
Далі йде M рядків, які задають розклад авіарейсів. i-й рядок містить три натуральних числа: S_i, F_i та P_i, де S_i - номер міста, з якого вилітає i-й рейс, F_i - номер міста, у яке прилітає i-й рейс, P_i - вартість перельоту i-м рейсом. 1 ≤ S_i ≤ N, 1 ≤ F_i ≤ N, 1 ≤ P_i ≤ 10^6.
Вихідні дані
Виведіть одне число - мінімальну вартість шляху, який підходить для професора. Якщо професор не зможе за K ночей дістатися до конференції, виведіть число -1.