Профессору Форду необходимо попасть на международную конференцию. Он хочет потретить на дорогу наименьшее количестводенег, поэтому решил, что будет путешествовать исключительно ночными авиарейсами (чтобы не тратиться на ночевку в отелях), а днем будет осматривать достопримечательности тех городов, через которые он будет проезжать транзитом. Он внимательно изучил расписание авиаперелетов и составил набор подходящих авиарейсов, выяснив, что перелеты на выбранных направлениях совершаются каждую ночь, и за одну ночь он не сможет совершить два перелета.
Теперь профессор хочет найти путь наименьшей стоимости, учитывая, что до конференции осталось K ночей (то есть профессор может совершить не более K перелетов).
Формат входных данных
В первой строке находятся числа N (количество городов), M (количество авиарейсов),
K (количество оставшихся ночей), S (номер города, в котором живет профессор),
F (номер города, в котором проводится конференция). Ограничения:
2≤N≤100, 1≤M≤100000, 1≤K;le&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 |