Arrda has a variety of electrical appliances and data cables at home, and many of the appliances have different types of plugs. This often causes Arrda to spend a lot of time finding the right data cable for sharing data between two appliances, and sometimes these cables are quite expensive!

Therefore, Arrda wants you to find the least expensive data conversion solution.

Problem Description

Arrda's home has \( n \) types of data cable connectors, with \( 2n \) varieties in total. Each type has 2 different connectors, labeled as \( i \) and \( n+i \). Only connectors of the same type can be connected to each other (you can think of \( i \) as a protruding connector and \( n+i \) as a recessed connector, which can be plugged together).

The store sells \( m \) types of bidirectional data cables, each with a connector at both ends, labeled as \( u_i \) and \( v_i \). Additionally, the \( i \)-th type of data cable has a purchase price \( w_i \), and each type of cable can be purchased in unlimited quantities.

Arrda wants to exchange data between two appliances with connector types \( S \) and \( T \). Find the minimum total cost to enable these two appliances to be directly connected or connected through several data cables (since buying cables requires money). If there is no solution, output I have no idea how to solve it.. Note that the connectors of the two appliances cannot be directly connected with a data cable because they are on the appliances, not at the ends of the data cables!

Input Format

The first line contains two integers \( n \) and \( m \), as described in the problem statement.

The next \( m \) lines each contain three integers \( u_i \), \( v_i \), and \( w_i \).

The last line contains two integers \( S \) and \( T \).

Output Format

A non-negative integer representing the minimum total cost to enable the two appliances to be directly connected or connected through several data cables.

If there is no solution, output I have no idea how to solve it..

Sample Input and Output

Sample Input #1

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

Sample Output #1

8

Sample Input #2

4 1
2 3 1
1 8

Sample Output #2

I have no idea how to solve it.

Sample Input #3

4 1
2 3 1
1 5

Sample Output #3

0

Sample Input #4

5 10
1 2 603124134
2 3 373980902
2 4 6578324
3 5 936364479
4 6 182080546
4 7 340293479
6 8 753053273
1 9 274129271
3 10 616764767
4 6 255802600
1 2

Sample Output #4

3673658542

Explanation of Samples

Sample 1 Explanation:

1=5->6=2->3=7->8=4

It can be proven that there is no solution with a lower total cost.

Sample 4 Explanation

1=6->8=3->5=10->3=8->6=1->9=4->7=2

For the 4->6 connection, there are two types of cables available, and we choose the one with the cost of \( 182080546 \) because it is cheaper.

It can be proven that there is no solution with a lower total cost.

Data Range

For \( 100\% \) of the data, \( 1 \le n, m \le 10^5 \), \( 1 \le u_i, v_i, s, t \le 2 \times n \), \( 1 \le w_i \le 10^9 \).

见题面 Input 部分

见题面 Output 部分