Профессору Форду необходимо попасть на международную конференцию. Он хочет потратить на дорогу наименьшее количество денег, поэтому решил, что будет путешествовать исключительно ночными авиарейсами (чтобы не тратиться на ночёвку в отелях), а днём будет осматривать достопримечательности тех городов, через которые он будет проезжать транзитом. Он внимательно изучил расписание авиаперелётов и выбрал подходящие авиарейсы, выяснив, что перелёты на выбранных направлениях совершаются каждую ночь и за одну ночь он не сможет совершить два перелёта. Теперь профессор хочет найти путь наименьшей стоимости, учитывая, что до конференции осталось \textbf{K} ночей (то есть профессор может совершить не более \textbf{K }перелётов). \InputFile В первой строке находятся числа \textbf{N} (количество городов), \textbf{M} (количество авиарейсов), \textbf{K} (количество оставшихся ночей), \textbf{S} (номер города, в котором живёт профессор), \textbf{F} (номер города, в котором проводится конференция). Ограничения: \textbf{2} ≤ \textbf{N} ≤ \textbf{100}, \textbf{1} ≤ \textbf{M} ≤ \textbf{10^5}, \textbf{1} ≤ \textbf{K} ≤ \textbf{100}, \textbf{1} ≤ \textbf{S} ≤ \textbf{N}, \textbf{1} ≤ \textbf{F} ≤ \textbf{N}. Далее идёт \textbf{M} строк, задающих расписания авиарейсов. \textbf{i}-я строка содержит три натуральных числа: \textbf{S_i}, \textbf{F_i} и \textbf{P_i}, где\textbf{S_i} - номер города, из которого вылетает \textbf{i}-й рейс, \textbf{F_i} - номер города, в который прилетает \textbf{i}-й рейс, \textbf{P_i} - стоимость перелёта \textbf{i}-м рейсом. \textbf{1} ≤ \textbf{S_i} ≤ \textbf{N}, \textbf{1} ≤ \textbf{F_i} ≤ \textbf{N}, \textbf{1} ≤ \textbf{P_i} ≤ \textbf{10^6}. \OutputFile Выведите одно число - минимальную стоимость пути, подходящего для профессора. Если профессор не сможет за \textbf{K}ночей добраться до конференции, выведите число \textbf{-1}.