Background

Arrda has many different kinds of electrical appliances and data cables at home, and many appliances use different plug types. This causes Arrda to spend a long time each time they want to share data between two appliances just to buy a suitable cable, and sometimes the cables are expensive.

So Arrda wants you to find the data conversion plan that costs the least money.

Problem Description

There are $n$ plug categories in Arrda’s home, and $2n$ types of cable connectors. Each category has $2$ different connector types, numbered $i$ and $n+i$. Only the two different connectors of the same category can be connected to each other (you may think of $i$ as a protruding connector and $n+i$ as a recessed connector; being connectable means “plugging in”).

The store sells $m$ kinds of bidirectional cables. Each bidirectional cable has one connector on each end, of types $u_i$ and $v_i$. The $i$-th kind of bidirectional cable has a purchase price $w_i$. Each kind of cable can be bought in unlimited quantity.

Arrda wants to exchange data between two appliances. The connector type numbers of the two appliances are $S, T$. Find the minimum total price that makes these two appliances connectable directly or via several cables (after all, buying cables costs money). If there is no solution, output I have no idea how to solve it.. Note that the interfaces on the two appliances cannot directly connect to a cable, because they are on the appliances, not on the ends of a cable.

Input Format

The first line contains two integers $n, m$, with the meaning given in the statement.

The next $m$ lines each contain three integers $u_i, v_i, w_i$.

The next line contains two integers $S, T$.

Output Format

Output a non-negative integer, representing the minimum total price that makes the two appliances connectable directly or via several cables.

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

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

8

4 1
2 3 1
1 8

I have no idea how to solve it.

4 1
2 3 1
1 5

0

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

3673658542

Hint

Explanation for Sample 1:

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

It can be proven that there is no plan with a smaller total cost.

Explanation for Sample 4

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

There are two kinds of cables for 4->6. We choose the one with cost $182080546$, because it is cheaper.

It can be proven that there is no plan with a smaller total cost.

Constraints

For $100\%$ of the testdata: $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$.

Translated by ChatGPT 5