라우팅

Bob은 회사 IT 보안팀에 새로 들어가서, 사무실 사이의 메시지가 인터넷을 얼마나 빨리 오가는지 추적하는 일을 맡았다. 일부 사무실은 아직 공사 중이라 전송 속도를 직접 재볼 수 없다. 그래서 Bob은 메시지 전달에 관여할 수 있는 서버의 지도를 그리고, 각 서버가 메시지 하나를 처리하는 데 걸리는 시간을 모았다. 메시지의 총 처리 시간은 보내는 서버, 경로 위의 모든 서버, 받는 서버의 처리 시간을 전부 더한 값이다. 메시지는 총 처리 시간이 가장 작은 경로로 전달된다.

여기까지는 쉬워 보였지만 Bob은 정보기관을 잊고 있었다. 인터넷의 서버는 저마다 어떤 기관이 관리하고, 그 기관이 어떤 패킷을 넘기고 어떤 패킷을 넘기지 않을지 정한다. 모든 서버는 들어오는 데이터를 빠짐없이 읽지만, 그중 일부만 다른 서버로 내보낸다.

각 서버는 서버 쌍의 목록을 갖고 있다. 쌍의 첫 번째 서버에서 바로 넘어온 메시지는 두 번째 서버로 보내지 않는다는 뜻이다. 이 규칙 아래에서 1번 서버를 떠난 메시지가 $n$번 서버에 닿기까지 걸리는 최소 총 처리 시간을 구하라.

메시지는 같은 서버를 두 번 이상 지나갈 수 있고, 지날 때마다 그 서버의 처리 시간이 다시 더해진다.

첫 줄에 서버의 개수 $n$ ($2 \le n \le 100$)이 주어진다. 서버에는 1번부터 $n$번까지 번호가 붙어 있다.

이어서 서버를 설명하는 블록이 1번 서버부터 $n$번 서버까지 순서대로 $n$개 주어진다. $i$번 서버를 설명하는 블록은 다음과 같다.

• 첫 줄에 두 정수 $m$ ($0 \le m \le n-1$)과 $t$ ($0 \le t \le 1000$)가 주어진다. $m$은 이 서버에서 나가는 연결의 개수, $t$는 이 서버의 처리 시간이다.
• 다음 $m$개의 줄에는 두 정수 $s$ ($0 \le s \le n-1$)와 $x$ ($1 \le x \le n$), 그리고 서로 다른 정수 $a_1, \ldots, a_s$ ($1 \le a_j \le n$, 모든 $j$에 대해 $a_j \ne i$)가 주어진다. $i$번 서버는 $x$번 서버로 메시지를 보내지만, $a_1, \ldots, a_s$ 중 한 서버에서 $i$번 서버로 바로 넘어온 메시지는 보내지 않는다.

메시지는 1번 서버에서 출발해 $n$번 서버로 간다.

1번 서버와 $n$번 서버를 포함해, 메시지가 지나는 서버의 처리 시간을 모두 더한 값의 최솟값을 출력한다. 그런 경로가 없으면 impossible을 출력한다.

그림은 두 예제 입력을 나타낸 것이다.