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

4 4
0 1 5
1 2 5
0 2 20
2 3 1
0 3 3

11

4 4
0 1 5
1 2 5
0 2 20
2 3 1
0 3 2

21