Write a program that, given a directed graph with postive and/or negative costs at the arcs (but no negative cycles), and two vertices x and y, computes the minimum cost to go from x to y.

Input

Input consists of several cases.
Every case begins with the number of vertices n
and the number of arcs m.
Follow m triples u, v, c,
indicating that there is an arc u → v of cost c,
where u ≠ v, −1000 ≤ c ≤ 1000 and c≠ 0.
Finally, we have x and y.
Assume 1 ≤ n ≤ 10^{4},
0 ≤ m ≤ 5n,
and that for every pair of vertices u and v
there is at most one arc of the kind u → v.
All numbers are integers.
Vertices are numbered from 0 to n−1.
The directed graph has no negative cycles.

Output

For every case, print the minimum cost to go from x to y, if this is possible. If there is no path from x to y, state so.

Public test cases

**Input**

6 10 1 0 6 1 5 15 3 4 3 3 1 8 4 0 20 0 5 5 0 2 1 5 1 10 4 1 2 2 3 4 3 5 2 1 0 1 1000 1 0 8 11 0 1 10 0 7 8 1 5 2 2 1 1 2 3 1 3 4 3 4 5 -1 5 2 -2 6 5 -1 6 1 -4 7 6 1 0 1

**Output**

16 no path from 1 to 0 5

Information

- Author
- Jordi Petit
- Language
- English
- Official solutions
- C++
- User solutions
- C++