Авиаперелеты
Профессору Форду необходимо попасть на международную конференцию. Он хочет потратить на дорогу наименьшее количество денег, поэтому решил, что будет путешествовать исключительно ночными авиарейсами (чтобы не тратиться на ночёвку в отелях), а днём будет осматривать достопримечательности тех городов, через которые он будет проезжать транзитом. Он внимательно изучил расписание авиаперелётов и выбрал подходящие авиарейсы, выяснив, что перелёты на выбранных направлениях совершаются каждую ночь и за одну ночь он не сможет совершить два перелёта.
Теперь профессор хочет найти путь наименьшей стоимости, учитывая, что до конференции осталось 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.