This problem has three extra sample files you can refer to, each of which can be found here.

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 (here, a simple cycle means a cycle such that no cities are visited twice except the start) may be represented 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 connected directly by a road, city ~c_1~ and city ~c_l~ are connected directly by a road, and for all ~1 \le i < j \le l~, we have ~c_i \ne c_j~. If ~l > 3~, then the roads satisfy the following additional constraint: there exist two non-adjacent cities on the cycle such that the two cities are directly connected by a road, or in other words, there exists ~1 \le u < v \le l~ such that ~v-u \ge 2~, ~u,v~ are not ~1~ and ~l~ simultaneously, and city ~c_u~ and city ~c_v~ are directly connected by a road.

Now the country is going to find a route to renovate between city ~s~ and city ~t~. Since the road will be inaccessible during renovation, the country wants to make sure it is possible to reach all other cities starting from any city in the country via the remaining roads during renovation (i.e. roads that are not included in the route to be renovated).

Please find a possible route to renovate and make sure the length is as short as possible.

Input Specification

The first line contains two integers ~n,m~ denoting the number of cities and the number of roads. The following ~m~ lines contain three integers ~u_i,v_i,w_i~ each denoting the endpoints of the roads and the lengths. It is guaranteed that each road connects two different cities, or in other words, ~u_i \ne v_i~. The last line contains two integers ~s,t~ denoting the endpoints of the route to be renovated.

Output Specification

The output contains only one integer denoting the minimum possible length of the route to be renovated satisfying the constraints specified in the problem. If there are no feasible solutions, output -1.

Sample Input 1

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

Sample Output 1

6

The route to be renovated is ~1 \to 3 \to 4~.

Sample Input 2

2 1
1 2 1
1 2

Sample Output 2

-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~, ~1 \le w_i \le 10^9~.
It is guaranteed for any two roads their endpoints are not entirely the same.
It is guaranteed the roads satisfy the conditions specified in the problem.

Test Case	~n \le~	~m \le~	Additional Constraints
1~6	~2000~	~4000~	None.
7~10	~5 \times 10^5~	~10^6~	The roads have equal lengths.
11~15			All roads satisfying ~w_i = 1~ form a path from ~s~ to ~t~, and the endpoints of the roads with ~w_i \ne 1~ have distance 2 on the path.
16~20			None.