A freight system has n depots (numbered 0 to n-1) connected by one-way cargo legs, each with a positive integer cost. A shipment plan is a walk that begins at depot s, follows legs in their allowed direction, and may revisit depots and reuse legs.
Given a required number of legs , find the minimum total cost of a walk from to that uses exactly legs (exactly edges, counting repeats). If no walk of exactly legs ends at , report that it is impossible. Note that may be : a zero-leg walk stays at , so it reaches (with cost ) only when equals .
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 depot u to depot v with cost w.
Final line: three integers s t L.
Output format
A single integer: the minimum total cost of a walk from s to t using exactly L legs, or -1 if none exists.
Constraints
- 1 <= n <= 200
- 0 <= m <= 2000
- 0 <= s, t, u, v <= n-1
- 0 <= L <= 200
- 1 <= w <= 100000