P10535 [Opoi 2024] Data Conversion

  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.

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.**

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 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.`.

### 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