Road

There are $n$ cities in a country connected by $m$ bidirectional roads. The cities are numbered $1, 2, \dots, n$ and the roads are numbered $1, 2, \dots, m$. Road $i$ connects city $u_i$ and city $v_i$, and its length is $w_i$ meters. Starting from any city, you may reach any other city via the roads.

The roads are built in a special way. Formally, a simple cycle passing through $l$ roads (a simple cycle is a cycle in which no city is visited twice except the start) may be written as $c_1 \to c_2 \to \dots \to c_{l-1} \to c_l$ such that for all $1 \le i < l$, city $c_i$ and city $c_{i+1}$ are directly connected by a road, city $c_1$ and city $c_l$ are directly connected by a road, and for all $1 \le i < j \le l$, we have $c_i \ne c_j$. If $l > 3$, the roads must also satisfy this condition: there exist two non-adjacent cities on the cycle that are directly connected by a road. In other words, there exists $1 \le u < v \le l$ with $v-u \ge 2$, where $u$ and $v$ are not $1$ and $l$ at the same time, such that city $c_u$ and city $c_v$ are directly connected by a road.

The country plans to renovate the route between city $s$ and city $t$. The route is closed during renovation, so the remaining roads must still let you reach every other city from any city. Find a possible route to renovate with the smallest total length.

The first line contains two integers $n$ and $m$, the number of cities and the number of roads. Each of the next $m$ lines contains three integers $u_i$, $v_i$, and $w_i$, the endpoints and length of road $i$. Each road connects two different cities. The last line contains two integers $s$ and $t$, the endpoints of the route to be renovated.

Print one integer, the minimum possible length of the route to be renovated that satisfies the conditions above. If no feasible route exists, print $-1$.

For all test cases, $2 \le n \le 5 \times 10^5$, $2 \le m \le 10^6$, $s \ne t$, $1 \le u_i, v_i \le n$, $u_i \ne v_i$, and $1 \le w_i \le 10^9$. No two roads have the same pair of endpoints. The roads satisfy the conditions stated in the problem.