Задача "Авиаперелеты"

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

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

Формат входных данных
В первой строке находятся числа N (количество городов), M (количество авиарейсов), K (количество оставшихся ночей), S (номер города, в котором живет профессор), F (номер города, в котором проводится конференция). Ограничения: 2≤N≤100, 1≤M≤100000, 1≤K≤100, 1≤S≤N, 1≤F≤N.

Далее идет M строк, задающих расписание авиарейсов. i-ая строка содержит три натуральных числа: Si, Fi и Pi, где Si - номер города, из которого вылетает рейс номер i, Fi - номер города, в который прилетает рейс номер i, Pi - стоимость перелета этим рейсом. 1≤Si≤N, 1≤Fi≤N, 1≤Pi≤106.

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

Пример

Пример ввода Пример вывода
4 5 2 1 4
1 2 1
2 3 1
3 4 1
1 3 3
1 4 5
4