흰 토끼의 회중시계

흰 토끼의 회중시계는 0부터 12까지만 표시하고, 12를 지나면 다시 0으로 돌아온다. 토끼는 여행이 끝난 순간 시침이 가리키는 숫자를 그대로 여행 시간으로 적는다. 그래서 실제로 14시간이 걸린 여행도 시침이 1에 멈추므로 수첩에는 1로 적힌다. 결국 수첩에 적힌 시간은 실제로 걸린 시간을 13으로 나눈 나머지다.

이상한 나라에는 장소가 $N$개 있다. 두 장소를 직접 잇는 길은 많아야 하나이고, 그 길은 어느 방향으로 지나도 실제로 걸리는 시간이 같다. 길 하나의 실제 소요 시간은 1 이상 12 이하의 정수다.

토끼의 수첩에는 여행 기록이 $T$개 있다. 기록 하나는 시계에서 읽은 시간, 지나간 장소의 개수, 지나간 순서로 이루어진다. 같은 장소를 여러 번 지나갈 수도 있다. 순서에서 이웃한 두 장소는 직접 잇는 길로 연결되어 있고, 수첩에 나오는 길이 이상한 나라의 길 전체다.

앨리스는 지금 장소 $A$에 있고 장소 $R$에 있는 토끼 굴로 가려고 한다. $A$에서 $R$까지 가는 경로 가운데 실제로 걸리는 시간이 가장 짧은 값을 구하라.

수첩만으로 모든 길의 실제 소요 시간이 하나로 정해지고, $A$에서 $R$로 가는 경로가 적어도 하나 있다.

첫째 줄에 정수 $N$, $A$, $R$, $T$가 공백으로 구분되어 주어진다. $N$은 서로 다른 장소의 개수, $A$는 앨리스가 있는 장소, $R$은 토끼 굴이 있는 장소, $T$는 수첩에 적힌 여행 기록의 개수다. 장소는 1부터 $N$까지 번호로 구분한다.

다음 $T$개 줄에는 여행 기록이 한 줄에 하나씩 d p a1 a2 ... ap 형식으로 주어진다. $d$는 토끼가 시계에서 읽은 여행 시간, $p$는 지나간 장소의 개수, $a_1\ a_2\ \dots\ a_p$는 지나간 순서다.

앨리스가 토끼 굴까지 가는 데 실제로 걸리는 가장 짧은 시간을 정수 하나로 출력한다.

• $2 \le N \le 200$
• $1 \le A, R \le N$
• $1 \le T \le 500$
• $0 \le d \le 12$
• $2 \le p \le 800$
• $1 \le a_i \le N$
• 서로 다른 길은 많아야 200개다.
• 길 하나의 실제 소요 시간 $d_{ij}$는 $1 \le d_{ij} \le 12$인 정수다.