Description

Country C contains $n$ cities, connected by $m$ undirected roads. The cities are numbered from $1$ to $n$, and the roads are numbered from $1$ to $m$. Road $i$ connects cities $u_i$ and $v_i$, and its length is $w_i$ meters. Using these roads, starting from any city in Country C, one can reach all other cities.

People in Country C like traveling along cycles, but they do not like passing through too many roads, so the roads in Country C are built in a very special way. More specifically, for a simple cycle that passes through $l$ roads (i.e. a cycle that visits no repeated city except the starting city), it can be written as $c_{1} \rightarrow c_{2} \rightarrow \cdots \rightarrow c_{l} \rightarrow c_{1}$ (where for all $1 \leq i<l$, cities $c_i$ and $c_{i+1}$ are connected by a road; cities $c_l$ and $c_1$ are connected by a road; and for all $1 \leq i<j \leq l$, $c_{i} \neq c_{j}$). If $l > 3$, then the roads in Country C satisfy the following condition:

• There exist two non-adjacent cities $u$, $v$ on the cycle such that there is a road directly connecting them. That is, there exists $1 \leq u<v \leq l$ such that $v-u \geq 2$, $u$ and $v$ are not simultaneously $1$ and $l$, and there is a road directly connecting cities $c_u$ and $c_v$.

Now Country C has a new renovation plan. It needs to find a path between cities $s$ and $t$ to renovate. During the renovation, all roads on the path will be blocked. To ensure people’s daily life, Country C hopes that while renovating this path, using the remaining roads (i.e. the roads not included in the renovation path) can still satisfy: starting from any city in Country C, one can still reach all other cities.

Country C has found you, a master engineer. Please help Country C find a renovation path that satisfies the above requirements, and make the total length of the path as small as possible。

Input Format

The first line contains two integers $n$, $m$, representing the number of cities and the number of roads.

The next $m$ lines each contain three integers $u_i$, $v_i$, $w_i$, representing the two endpoints of each road and its length.

The testdata guarantees that each road connects two different cities, i.e. $u_i \not= v_i$.

The last line contains two integers $s$, $t$, representing the two endpoints of the path to be renovated.

Output Format

Output a single integer in one line, representing the minimum total length of a renovation path that satisfies the requirements.

If there is no path that satisfies the requirements, output one integer $-1$ in one line.

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

6

2 1
1 2 1
1 2

-1

Hint

Explanation for Sample 1

The path $(1,2,1),(2,3,1),(3,4,1)$ is the shortest path (by total length) between cities $1$ and $4$, but it does not satisfy the requirement.

The path $(1,3,5),(3,4,1)$ satisfies the requirement, with length $6$.

The path $(1,2,1),(2,4,6)$ satisfies the requirement, with length $7$.

Other than the two paths above, there is no other path that satisfies the requirement.

Sample 3

See road/road3.in and road/road3.ans in the contestant directory. This sample has the same constraints as test points $1 \sim 6$.

Sample 4

See road/road4.in and road/road4.ans in the contestant directory. This sample has the same constraints as test points $7 \sim 10$.

Sample 5

See road/road5.in and road/road5.ans in the contestant directory. This sample has the same constraints as test points $11 \sim 15$.

Sample 6

See road/road6.in and road/road6.ans in the contestant directory. This sample has the same constraints as test points $16 \sim 20$.

Constraints

For all test points: $2 \leq n \leq 5 \times 10^{5}$, $2 \leq m \leq 10^{6}$, $s \neq t$.

$1 \leq u_{i}, v_{i} \leq n$, $u_{i} \neq v_{i}$, $1 \leq w_{i} \leq 10^{9}$, and it is guaranteed that for any two roads, their endpoints are not both the same.

It is guaranteed that the given roads satisfy the property described in the second paragraph of the statement.

The detailed limits for each test point are shown in the table below:

Special constraint A: All roads have the same length.

Special constraint B: All roads with $w_i = 1$ form exactly one path from $s$ to $t$, and for every other road with $w_i \not= 1$, the distance between its two endpoints along this path is $2$.

Translated by ChatGPT 5