Mixed Flight Plans

Ad Hoc Postal Company (AHPC) delivers postal envelopes in a simple way. It advertises for a volunteer, buys that volunteer the cheapest flight plan from the source city to the destination city, and hands over a bag of envelopes at the source airport. The volunteer gives the bag to the company's correspondent at the destination airport.

Besides direct flights between two airports, there are indirect trips that stop at several airports in a fixed order. A passenger who buys an indirect trip has to board at its first airport and passes the airports one after another in the listed order, with no other direct flight or indirect trip in between. The passenger may give up the rest of the trip and get off at any intermediate airport. The price of an indirect trip is fixed, so it costs the same whether the passenger takes every flight of it or stops in the middle. A flight plan is built from direct flights and indirect trips (whole or partial), and its price is the sum of the prices of everything bought for it.

Two bags have to be sent, one from airport $A$ to $B$ and the other from $C$ to $D$, where $A$, $B$, $C$, $D$ are four different airports. The company picks one of these two arrangements.

• Buy a plan from $A$ to $B$ for the first volunteer and a plan from $C$ to $D$ for the second one.
• Mix the two plans to save money. Buy a plan from $A$ to $D$ for the first volunteer and a plan from $C$ to $B$ for the second one. If both plans stop at the same airport $M$, the two volunteers meet at $M$ and exchange their bags, so the first one carries the second bag to $D$ and the second one carries the first bag to $B$.

$M$ may be one of $A$, $B$, $C$, $D$, and it may also be an airport that a volunteer only passes while riding an indirect trip, without getting off there. The first volunteer has to pass $M$ before arriving at $D$, and the second one has to pass $M$ before arriving at $B$. The total price is the price of the first plan plus the price of the second plan.

The figure above shows six airports with direct flights (solid arrows), indirect trips (dashed and dotted arrows), and their prices. One bag goes from airport 3 ($A$) to 5 ($B$), the other from 6 ($C$) to 1 ($D$). If the company buys (3,4) and (4,5) for the first volunteer and (6,5) and (5,1) for the second one, the total price is 300. A cheaper choice is (3,4,1,2,6) for the first volunteer and (6,2) with (2,4,5) for the second one, for a total of 250. The volunteers meet at airport 4 ($M$) and swap bags there, and the first volunteer leaves the indirect trip at airport 1.

Given the flight information, write a program that finds the cheapest cost of delivering the two bags.

The input has several test cases. The first line of each case has six integers $n$, $m$, $A$, $B$, $C$, $D$. $n$ ($4 \le n \le 100$) is the number of airports, numbered 1 through $n$. $m$ ($0 \le m \le 10\,000$) is the number of direct flights and indirect trips together.

The $i$th of the next $m$ lines starts with two positive integers $p_i$ and $s_i$. $p_i$ ($p_i \le 10^6$) is the price, and $s_i$ is 1 for a direct flight and 2 or more for an indirect trip. Then come $s_i + 1$ distinct airport numbers in the order they are visited.

The line after the last case is 0 0 0 0 0 0, which must not be processed.

For each test case, print the cheapest delivery cost on one line. If neither arrangement above can deliver both bags, print Impossible! without the quotes.