The most short-circuit write 2

Time Limit: 10000 ms Memory Limit: 524288 k
Total Submit: 14 Accepted: 2
Case Time Limit: 1000 ms

The Description

There are negative rights have nothing to figure, specify the shortest path between two points,

Input

Input: the first line, the two Numbers n and m, said n vertices, m side
The next m lines, each line three integers, the beginning and end of the edge respectively the length of the side
The last line of two integers x y said for the shortest path from point to point x y

The Output

Output: a line, an integer, the shortest path length

The Sample Input


3 3
1 2 5
1 2 3
3 2 1
1
2The Sample Output


3
Hint

N<=400000
m<=2000000
Node number from 1 to n
The length of each edge is an integer 0 to 109