A shipping network has n distribution hubs, numbered 0 to n - 1, and m one-way
cargo legs. Leg i moves cargo from hub u to hub v for a total handling-and-transport fee of w.
Multiple legs between the same pair of hubs may exist, at different fees.
Given a source hub s, a destination hub t (with s != t), and a maximum number of legs k that a
shipment is allowed to use, print the minimum total fee to move cargo from s to t using AT MOST k
legs. If no such route exists within the leg budget, print -1 instead.
Input format
Line 1: two integers n m.
Next m lines: three integers u v w -- a directed cargo leg from hub u to hub v costing w
(hubs are 0-indexed).
Last line: three integers s t k.
Output format
A single integer: the minimum total fee from s to t using at most k legs, or -1 if impossible.
Constraints
- 2 <= n <= 200
- 0 <= m <= 800
- 0 <= u, v < n, u != v
- 1 <= w <= 1000
- 0 <= s, t < n, s != t
- 0 <= k < n