Flights#4456
Professor Ford needs to attend an international conference and wishes to minimize his travel expenses. To save on hotel accommodation, he decides to travel exclusively by night flights and spend his days sightseeing in the cities he passes through in transit. He carefully studies the flight schedules and selects suitable night flights. He learns that, for the selected directions, flights operate every night and that he cannot make more than one flight per night.
The task is to determine the minimum-cost path for Professor Ford to attend the conference, given that there are nights remaining before the conference (that is, the professor can make at most flights).
The first line contains five integers: (the number of cities), (the number of flights), (the number of nights remaining), (the number of the city where the professor lives), and (the number of the city where the conference is being held).
Constraints: 2 \leq N \leq 100, 1 \leq M \leq 10^5, 1 \leq K \leq 100, 1 \leq S \leq N, 1 \leq F \leq N.
The next lines describe the flight schedule. Each line contains three integers: S_i, F_i, and P_i, where S_i is the departure city of the -th flight, F_i is the arrival city, and P_i is the cost of the -th flight.
Constraints: 1 \leq S_i \leq N, 1 \leq F_i \leq N, 1 \leq P_i \leq 10^6.
Output a single number: the minimum possible cost of a path suitable for the professor. If it is not possible to reach the conference city within nights, output .
Пример 1