You are given a directed graph of flights, where each flight goes from one city to another for a given price. Find the cheapest total price to travel from src to dst using at most k intermediate stops (so at most k + 1 flights). If it cannot be done within k stops, output -1.
Input format
Line 1: five integers n m src dst k. Cities are numbered 0..n-1.
Next m lines: three integers u v w meaning a directed flight from u to v costing w.
Output format
One line: the minimum total price, or -1 if unreachable within k stops.
Constraints
- 1 <= n <= 100
- 0 <= m <= 2000
- 0 <= src, dst < n, src != dst
- 0 <= k <= n
- 1 <= w <= 10000