Авиаперелеты

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

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

Входные данные

В первой строке входного файла INPUT.TXT находятся целые числа N, M, K, S и F – количество городов, количество авиарейсов, количество оставшихся ночей, номер города, в котором живет профессор, номер города, в котором проводится конференция соответственно (2 ≤ N ≤ 100, 1 ≤ M ≤ 10⁵, 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⁶).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – минимальную стоимость пути, подходящего для профессора. Если профессор не сможет за K ночей добраться до конференции, выведите число -1.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!