Flights
Professor Ford is planning to attend an international conference and aims to minimize his travel expenses. To save on accommodation costs, he has decided to travel only on night flights, allowing him to explore the cities during the day. After reviewing the flight schedules, he has identified suitable flights that operate nightly, ensuring he takes only one flight per night.
The challenge is to determine the least expensive route for the professor, given that there are K nights remaining before the conference, meaning he can take at most K flights.
Input
The first line contains five integers: N (the number of cities), M (the number of flights), K (the number of nights left), S (the city where the professor resides), and F (the city where the conference is held). The constraints are as follows: 2 ≤ N ≤ 100, 1 ≤ M ≤ 10^5, 1 ≤ K ≤ 100, 1 ≤ S ≤ N, 1 ≤ F ≤ N.
Following this, there are M lines detailing the flight schedule. Each line contains three integers: S_i, F_i, and P_i, where S_i is the departure city of the i-th flight, F_i is the arrival city, and P_i is the cost of the flight. The constraints are: 1 ≤ S_i ≤ N, 1 ≤ F_i ≤ N, 1 ≤ P_i ≤ 10^6.
Output
Output a single number representing the minimum cost of the route that suits the professor's requirements. If it is not possible for the professor to reach the conference city within K nights, output -1.