Data Cable Connection

Arrda has n categories and a total of 2n types of data cable connectors. For each category i (1 ≤ i ≤ n), there are two types: i and n+i. Only the two different connectors from the same category – that is, i and n+i – are complementary (you can think of i as the protruding (male) connector and n+i as the recessed (female) connector, so that only these two can connect).

The store sells m types of bidirectional data cables. The i-th cable has two connector types u_i and v_i and costs w_i dollars. An unlimited number of each cable is available.

You are given two appliances whose connector types are S and T, respectively. Note: The two appliance connectors cannot be connected directly (because they are built into the appliances). Instead, to attach a cable you must plug one of its ends into an appliance. In order for a cable to be attached to an appliance with connector x, the cable must have a connector equal to the complement of x (so that it fits the appliance). The complement function is defined in latex as follows:

$$\mathrm{comp}(x)=\begin{cases} x+n, & 1\le x \le n,\\ x-n, & n+1 \le x \le 2n. \end{cases} $$

A cable can be attached in either orientation. When a cable is used, think of it as contributing a transition: if you are at some connector state x, you may attach a cable whose one end equals \(\mathrm{comp}(x)\); once attached, the other end of the cable becomes your new free cable-end state.

More formally, you are allowed to make a transition from a free state x to a new free state y by purchasing a cable with connector pair \((u,v)\) at cost w if either \(\mathrm{comp}(x)=u\) (in which case y=v) or \(\mathrm{comp}(x)=v\) (in which case y=u). Initially, you do not have a free cable‐end; instead, the two appliances have fixed connectors S and T. To attach the first cable to the appliance with connector S, you must purchase a cable whose one connector equals \(\mathrm{comp}(S)\). Similarly, after a sequence of cable purchases, if your free state becomes \(\mathrm{comp}(T)\), you can complete the connection by attaching that cable end to the appliance with connector T.

Your task is to determine the minimum total cost needed (i.e. the sum of the costs of cables purchased) to connect the two appliances (using one or more cables). If no valid sequence of cable purchases exists that connects the two appliances, output I have no idea how to solve it.

inputFormat

The first line contains two integers n and m (the number of categories and the number of cable types, respectively). The next m lines each contain three integers u_i, v_i, and w_i – representing a cable that has two connector types and its cost. The last line contains two integers S and T, which are the connector types of the two appliances.

outputFormat

Output the minimum total cost required to connect the two appliances using one or more cables. If connecting them is impossible, output I have no idea how to solve it.

sample

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

I have no idea how to solve it.