교차 항공 일정

AHPC(Ad Hoc Postal Company)는 우편물을 이렇게 배달한다. 자원봉사자를 모집해서 출발 도시에서 도착 도시까지 가는 가장 싼 항공 일정을 사 주고, 출발 공항에서 봉투가 든 가방을 건네준다. 자원봉사자는 도착 공항에서 회사 담당자에게 그 가방을 넘긴다.

공항 사이에는 두 공항을 바로 잇는 직항편도 있고, 여러 공항을 정해진 순서로 지나가는 경유 일정도 있다. 경유 일정을 산 승객은 반드시 첫 번째 공항에서 타야 하고, 일정에 적힌 순서대로 공항을 연달아 지나간다. 중간에 다른 직항편이나 다른 경유 일정을 끼워 넣을 수는 없다. 대신 남은 구간을 포기하고 어느 경유 공항에서든 내릴 수 있다. 경유 일정의 가격은 고정이어서, 전 구간을 다 타든 중간에 내리든 같은 값을 낸다. 항공 일정은 직항편과 경유 일정(전 구간 또는 일부 구간)을 이어 붙여 만들고, 그 가격은 사들인 직항편과 경유 일정의 가격을 모두 더한 값이다.

가방 두 개를 보내야 한다. 하나는 공항 $A$에서 $B$로, 다른 하나는 $C$에서 $D$로 가야 한다 ($A$, $B$, $C$, $D$는 서로 다른 공항이다). 회사는 다음 두 방법 중 하나를 고른다.

• 첫 번째 자원봉사자에게 $A$에서 $B$까지 가는 일정을, 두 번째 자원봉사자에게 $C$에서 $D$까지 가는 일정을 사 준다.
• 비용을 아끼려고 두 일정을 교차시킨다. 첫 번째 자원봉사자에게 $A$에서 $D$까지, 두 번째 자원봉사자에게 $C$에서 $B$까지 가는 일정을 사 준다. 두 일정이 같은 공항 $M$에 들르면 두 사람은 $M$에서 만나 가방을 맞바꾼다. 그러면 첫 번째 사람이 두 번째 가방을 $D$로, 두 번째 사람이 첫 번째 가방을 $B$로 가져간다.

$M$은 $A$, $B$, $C$, $D$ 중 하나여도 되고, 경유 일정을 탄 채로 내리지 않고 지나가기만 하는 공항이어도 된다. 단 첫 번째 사람은 $D$에 도착하기 전에 $M$을 지나야 하고, 두 번째 사람은 $B$에 도착하기 전에 $M$을 지나야 한다. 전체 가격은 두 일정의 가격을 더한 값이다.

위 그림은 공항 여섯 개와 직항편(실선 화살표), 경유 일정(파선 화살표와 점선 화살표), 그리고 각각의 가격을 보여 준다. 가방 하나는 공항 3($A$)에서 5($B$)로, 다른 하나는 6($C$)에서 1($D$)로 가야 한다. 회사가 첫 번째 자원봉사자에게 (3,4)와 (4,5)를, 두 번째 자원봉사자에게 (6,5)와 (5,1)을 사 주면 가격은 합쳐서 300이다. 더 싼 방법은 첫 번째 자원봉사자에게 (3,4,1,2,6)을, 두 번째 자원봉사자에게 (6,2)와 (2,4,5)를 사 주는 것으로, 합쳐서 250이다. 두 사람은 공항 4($M$)에서 만나 가방을 바꾸고, 첫 번째 자원봉사자는 공항 1에서 경유 일정을 그만둔다.

항공편 정보가 주어질 때 가방 두 개를 배달하는 최소 비용을 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스의 첫 줄에 정수 여섯 개 $n$, $m$, $A$, $B$, $C$, $D$가 주어진다. $n$($4 \le n \le 100$)은 공항의 수이고, 공항 번호는 1번부터 $n$번까지다. $m$($0 \le m \le 10\,000$)은 직항편과 경유 일정을 합한 수다.

다음 $m$개 줄 중 $i$번째 줄은 양의 정수 $p_i$와 $s_i$로 시작한다. $p_i$($p_i \le 10^6$)는 가격이고, $s_i$는 직항편이면 1, 경유 일정이면 2 이상이다. 그 뒤에 방문하는 순서대로 서로 다른 공항 번호 $s_i + 1$개가 주어진다.

마지막 케이스 다음 줄에는 0 0 0 0 0 0이 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 가장 싼 배달 비용을 한 줄에 출력한다. 위의 두 방법 중 어느 쪽으로도 가방 두 개를 모두 배달할 수 없으면 Impossible!을 (따옴표 없이) 출력한다.