Country C contains $n$ cities connected by $m$ bidirectional roads. The cities are numbered from $1$ to $n$, and the roads are numbered from $1$ to $m$. Road $i$ connects city $u_i$ and city $v_i$ and has a length of $w_i$ meters. Using these roads, it is possible to travel from any city in Country C to all other cities.

The people of Country C enjoy loop journeys but dislike passing through too many roads. For this reason, the roads in Country C are constructed in a very specific way. More specifically, for a simple loop (a loop that does not pass through any repeated cities except for the starting city) consisting of $l$ roads, which can be represented as $c_1 \to c_2 \to \dots \to c_l \to c_1$ (where for all $1 \le i < l$, city $c_i$ is connected to city $c_{i+1}$ by a road; city $c_l$ is connected to city $c_1$ by a road; and for all $1 \le i < j \le l$, $c_i \neq c_j$), if $l > 3$, the roads of Country C satisfy the following condition: * There exist two non-adjacent cities $u, v$ on the loop that are directly connected by a road. That is, there exist $1 \le u < v \le l$ such that $v - u \ge 2$, $u$ and $v$ are not simultaneously $1$ and $l$, and city $c_u$ and city $c_v$ are directly connected by a road.

Country C now has a new renovation plan: it needs to find a path between city $s$ and city $t$ to renovate. All roads included in the renovation path will become impassable. To ensure the daily lives of the people, Country C hopes that when this path is renovated, the remaining roads (i.e., the roads not included in the renovation path) still satisfy the condition: it is possible to travel from any city in Country C to all other cities.

Country C has found you, an engineering master, to help them find a renovation path that satisfies the above requirements while minimizing the total length of this path.

Input

Read data from the file road.in. The first line contains two integers $n$ and $m$, representing the number of cities and the number of roads, respectively. The next $m$ lines each contain three integers $u_i, v_i, w_i$, representing the two endpoints and the length of each road, respectively. It is guaranteed that every road connects two different cities, i.e., $u_i \neq v_i$. The last line contains two integers $s$ and $t$, representing the two endpoints of the path to be renovated.

Output

Output to the file road.out. A single integer representing the minimum total length of the renovation path that satisfies the requirements. If no such path exists, output $-1$.

Examples

Input 1

4 5
1 2 1
2 3 1
3 4 1
1 3 5
2 4 6
1 4

Output 1

6

Note 1

The path $(1, 2, 1), (2, 3, 1), (3, 4, 1)$ is the shortest path between city $1$ and city $4$, but it does not satisfy the requirements. The path $(1, 3, 5), (3, 4, 1)$ satisfies the requirements, with a length of $6$. The path $(1, 2, 1), (2, 4, 6)$ satisfies the requirements, with a length of $7$. Apart from these two paths, there are no other paths that satisfy the requirements.

Input 2

2 1
1 2 1
1 2

Output 2

-1

Examples 3-6

See the files road/road3.in through road/road6.in and their corresponding .ans files in the contestant directory. These examples have the same constraints as test cases $1 \sim 6$, $7 \sim 10$, $11 \sim 15$, and $16 \sim 20$ respectively.

Constraints

For all test cases: $2 \le n \le 5 \times 10^5$, $2 \le m \le 10^6$, $s \neq t$. $1 \le u_i, v_i \le n$, $u_i \neq v_i$, $1 \le w_i \le 10^9$. It is guaranteed that no two roads have the same set of endpoints. It is guaranteed that the given roads satisfy the property described in the second paragraph of the problem statement. The specific constraints for each test case are as follows:

Special Constraint A: All road lengths are equal. Special Constraint B: All roads with $w_i = 1$ form exactly one path from $s$ to $t$, and for any other road with $w_i \neq 1$, its two endpoints are at a distance of $2$ along this path.