Description

Jasper is a competitive mountain biker preparing for a major downhill race. To enhance his chances of winning, Jasper commits to daily practice sessions on a specialized training circuit. The circuit is laid out as a directed weighted graph where each node represents a gate, and the directed edges signify the trails that link these gates. Each edge carries a weight that denotes the time Jasper takes to ride through that section of the trail.

The graph contains N vertices. There are two special vertices: one is the starting gate and the other is the finishing gate. Jasper needs to strategize his practice by finding the fastest path from the starting gate to the finishing gate, ensuring he passes through no more than K gates, not including both the start and finish.

Vertices within the graph are indexed beginning with 1.

Your mission is to calculate the least amount of time Jasper can record to complete the circuit while going through at most K gates. If Jasper cannot find a valid path within these constraints, the function should return -1.

Take the below graph as example. Let node 1 be the starting point and node 3 be the end line, and Jasper can only pass 2 vertices at most.

Although the minimum path from node 1 to node 3 is 1->4->2->5->3, which is 4 + 1 + 3 + 1 = 9, but it passes three vertices along the path. Therefore, this path cannot be the answer.

The final answer should be 1->4->2->3, which is 4 + 1 + 5= 10, and you should output 10.

Let’s see the other example below

There is another graph which is similar to the graph above. The difference is the direction of the blue edges. In this situation, if node 1 is the starting gate and the node 3 is the end gate as well, you can see that there is no way to go from node 1 to node 3. As a result, you should output -1.

Only vector are allowed to use.

Remember that the answer should be followed by a newline.

Input

The first line contains a pair of integers N and E, which are the numbers of nodes and edges, respectively.

The second line includes three integers, i.e., S, F, K, which specify the starting gate, finish gate, and the maximum number of nodes that can be passed, respectively.

The following E lines each contains a triplet U, V, W, which represents an edge from node U to node V with the time that it takes to pass, W (W is a positive integer).

1 <= N <= 10000

0 <= E <= N(N-1)

0<= S, F, K <= N

1 <= W <= 10000

Parameters above are all integers.

Output

Print the minimum time from the start gate to the finish gate by passing through at most K nodes. If there is no such a route, print -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss