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