문제

우솔이는 추운 겨울을 피해 따뜻한 곳으로 휴가를 떠나려 한다. 우솔이가 이용할 수 있는 항공사에는 $N$개의 비행 노선이 있으며, 각 노선은 복잡한 구조로 되어 있다.

항공사는 $N$개의 노선을 운영하며, 각 노선은 두 개 이상의 도시로 구성된 특정 경로를 비행한다. 예를 들어, 어떤 노선은 도시 $1$에서 시작하여 도시 $5$, 도시 $2$를 거쳐 도시 $8$에서 끝날 수 있다. 한 노선에서 같은 도시가 여러 번 등장하지는 않는다. 우솔이가 특정 노선을 이용하기로 했다면, 해당 경로에 있는 어떤 도시에서든 탑승할 수 있으며, 그보다 나중에 나오는 어떤 도시에서든 내릴 수 있다. 반드시 첫 번째 도시에서 탑승하거나 마지막 도시에서 내릴 필요는 없다. 각 노선에는 고정된 비용이 있으며, 우솔이가 노선의 일부라도 이용한다면 이 비용을 지불해야 한다. 이용하는 도시의 수는 비용에 영향을 주지 않는다. 또한, 우솔이는 각 노선을 최대 한 번만 이용할 수 있다.

우솔이는 현재 위치인 도시 $A$에서 목적지인 도시 $B$까지 가는 가장 저렴한 방법을 찾고 싶어 한다. 너무 복잡한 일정은 피하고 싶기에, 우솔이는 최대 두 개의 노선만을 이용하기로 했다. 우솔이가 지불해야 하는 최소 비용을 구하시오.

입력

첫째 줄에 출발 도시 번호 $A$, 도착 도시 번호 $B$, 그리고 노선의 수 $N$이 공백으로 구분되어 주어진다. ($1 eq A, B$; $1 eq A, B eq 10,000$; $1 eq N eq 500$)

이어서 $N$개의 노선 정보가 주어지며, 각 노선은 두 줄에 걸쳐 설명된다. 첫 번째 줄에는 노선 이용 비용과 노선에 포함된 도시의 수 $M$이 공백으로 구분되어 주어진다. ($1 eq ext{비용} eq 1,000$; $2 eq M eq 500$) 두 번째 줄에는 해당 노선이 지나는 $M$개의 도시 번호가 순서대로 공백으로 구분되어 주어진다. 각 도시 번호는 $1$ 이상 $10,000$ 이하의 정수이다.

출력

최대 두 개의 노선을 이용하여 도시 $A$에서 도시 $B$로 이동하는 데 필요한 최소 비용을 출력한다. 만약 이동할 수 있는 방법이 없다면 -1을 출력한다.

예제 입력 1

1 2 3
3 3
3 2 1
4 4
2 1 4 3
8 5
4 1 7 8 2

예제 출력 1

7