A parcel network has n sorting hubs, numbered 0 to n - 1, and m one-way transfer
legs. Leg i moves a parcel from hub u to hub v for a 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 total budget , print the FEWEST
number of legs a route from to can use while keeping the sum of its fees at most . If no
route from to ever costs at most (regardless of how many legs it uses), print instead.
Input format
Line 1: two integers n m.
Next m lines: three integers u v w -- a directed transfer leg from hub u to hub v costing w
(hubs are 0-indexed).
Last line: three integers s t C.
Output format
A single integer: the minimum number of legs needed to go from s to t for a total fee of at most
C, 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 <= C <= 1000000