A courier travels a weighted directed network of n waypoints (numbered 0 to n-1) connected by one-way legs, each with a positive integer toll. The courier holds k free-leg vouchers: on up to k of the legs used along the route, the toll may be waived (treated as 0). Vouchers are optional and each covers one traversal of one leg.
Starting at waypoint 0, find the minimum total toll to reach waypoint n-1, using at most k vouchers optimally. If waypoint n-1 cannot be reached, report that it is impossible.
Input format
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a one-way leg from u to v with toll w.
Final line: a single integer k, the number of free-leg vouchers.
Output format
A single integer: the minimum total toll from waypoint 0 to waypoint n-1 using at most k vouchers, or -1 if unreachable.
Constraints
- 1 <= n <= 20000
- 0 <= m <= 100000
- 0 <= u, v <= n-1
- 0 <= k <= 10
- 1 <= w <= 100000