An airline operates m one-way flights among n cities (numbered 0 to n-1). Each flight goes from one city to another for a positive integer fare.
A traveller wants to fly from city src to city dst using at most k layovers, where a layover is an intermediate city where the traveller changes flights. Using at most k layovers is exactly the same as taking at most k+1 flights in total. Find the minimum total fare of such a trip, or report that no valid trip exists.
Input format
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a one-way flight from city u to city v with fare w.
Final line: three integers src dst k.
Output format
A single integer: the minimum total fare using at most k layovers, or -1 if no such trip exists.
Constraints
- 1 <= n <= 1000
- 0 <= m <= 5000
- 0 <= src, dst, u, v <= n-1
- 0 <= k <= n
- 1 <= w <= 100000