You have won a lottery to go sightseeing at Santa's North Pole! Being very excited about this trip, you have procured a map of the sightseeing location and are planning the optimal route.

The North Pole is represented as a collection of $N$ locations numbered from $1$ to $N$, and $M$ tour routes between these locations. Each tour route is bidirectional and has a certain time $t$ that it takes to traverse. There is also a start location $S$ where the tour bus will drop you off and an end location $E$ where you will be picked up and flown home. Lastly, to make the North Pole more navigable, the designers ensured that every location is part of at most one cycle.

You wish to minimize the time you spend as you have an important CS club meeting right after the trip. However, you also want to see many locations, without going through much navigation. With this in mind, you have decided on a specific set of requirements for the optimal route:

1. The route must start and end at locations $S$ and $E$ respectively.
2. The route must pass through a simple cycle, which is defined as a non-empty path in which only the first and last vertices are equal, and there are no repeated edges or vertices (excluding the first and last vertex).
3. The route must be as short as possible in terms of the total traversal time while meeting requirements 1 and 2.

Given the map of the North Pole sightseeing location, and the locations $S$ and $E$, find the traversal time of the route that meets the given requirements.

Constraints

$2\le N,M\le 2\times {10}^5$

$1\le u,v\le N$

$1\le t\le 100$

$1\le S,E\le N$

As mentioned in the problem statement, it is guaranteed that every location will be part of at most one simple cycle.

Input Specification

The first line will contain two space-separated integers, $N$ and $M$, representing the number of locations and tour routes, respectively.

Each of the next $M$ lines will contain three space-separated integers, $u$, $v$, (such that $u\ne v$) and $t$, indicating that there is a tour route between locations $u$ and $v$ that takes $t$ minutes to traverse.

The final line will contain two space-separated integers, $S$ and $E$ (such that $S\ne E$), indicating the start and end locations, respectively.

Output Specification

Output a single integer on a single line: the traversal time of the route that meets the requirements in minutes. If there is no possible route that meets the requirements, output -1.

Sample Input 1

10 11
1 2 5
2 3 4
3 9 9
4 5 7
6 7 2
7 9 4
6 8 5
1 6 3
5 10 2
10 4 6
9 4 2
1 8

Sample Output 1

35

Explanation of Sample 1

This is the graph given in this sample case:

An optimal path that starts at location $1$ and ends at location $8$ while meeting the requirement is as follows:

$${\displaystyle 1\to 2\to 3\to 9\to 7\to 6\to 1\to 6\to 8}$$

By examining the times associated with the traversed routes, it is evident that the total time is $35$ minutes.

Sample Input 2

7 6
1 4 8
5 4 2
5 1 6
2 7 3
7 3 2
3 6 7
2 6

Sample Output 2

-1

Explanation of Sample 2

This is the graph given in this sample case:

It can be observed that there is no path from location $2$ to location $6$ that passes through a simple cycle, so the correct output is -1.