지하철 타기

Tom은 도시에서 한 역에서 다른 역으로 이동하기 위해 지하철을 타고 있다.

도시의 지하철 시스템은 다음과 같이 운영된다:

• 도시에는 N개의 지하철 노선이 있다: 1호선, 2호선, ..., N호선.

• 각 지하철 i에는 $SN_{i}$개의 역이 있다. 이 역들을 $S_{i,1}$,$S_{i,2}$, ... , S_{i,$SN_{i}$}라고 하자. 이 역들은 한쪽 종점에서 다른 쪽 종점까지 순서대로 놓여 있다. 지하철은 양방향으로 운행한다. 즉, 지하철은 $S_{i,1}$ -> $S_{i,2}$ -> ... -> S_{i,$SN_{i}$} 방향과 S_{i,$SN_{i}$} -> S_{i,$SN_{i}$-1} -> ... -> $S_{i,1}$ 방향으로 운행한다. 어느 역에서든 지하철을 타고 어느 역에서든 내릴 수 있다. 한 역에서 다음 역으로 이동하는 데는 일정한 시간이 걸린다. $S_{i,1}$에서 $S_{i,2}$까지 이동하는 데 $Time_{i,1}$분, $S_{i,2}$에서 $S_{i,3}$까지 이동하는 데 $Time_{i,2}$분이 걸리는 식이다. 반대 방향으로도 같은 시간이 걸린다.

• M개의 환승 터널이 있다. 각 환승 터널은 서로 다른 지하철 노선의 두 역을 연결한다. 터널을 어느 방향으로 통과하든 일정한 시간이 걸린다. 터널의 한쪽 끝에서 지하철을 내린 뒤 터널을 걸어서 다른 쪽 끝의 역으로 갈 수 있다.

• i호선의 지하철역에 도착하면 다음 지하철을 타기 위해 $W_{i}$분을 기다려야 한다.

이제 한 역에서 다른 역으로 이동하려고 한다. 필요한 최단 시간을 구한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ $W_{i}$ ≤ 100. 1 ≤ $Time_{i,j}$ ≤ 100. 1 ≤ $m1_{i}$ ≤ N. 1 ≤ $s1_{i}$ ≤ SN_{$m1_{i}$}. 1 ≤ $m2_{i}$ ≤ N. 1 ≤ $s2_{i}$ ≤ SN_{$m2_{i}$}. $m1_{i}$와 $m2_{i}$는 서로 다르다. 1 ≤ $t_{i}$ ≤ 100. 1 ≤ Q ≤ 10. 1 ≤ x1 ≤ N. 1 ≤ y1 ≤ $SN_{x1}$. 1 ≤ x2 ≤ N. 1 ≤ y2 ≤ $SN_{y2}$. $S_{x1,y1}$역과 $S_{x2,y2}$역은 서로 다르다.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ N ≤ 10. 0 ≤ M ≤ 10. 2 ≤ $SN_{i}$ ≤ 100. 각 테스트 케이스의 전체 역 수는 최대 100개이다.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ N ≤ 100. 0 ≤ M ≤ 100. 2 ≤ $SN_{i}$ ≤ 1000. 각 테스트 케이스의 전체 역 수는 최대 1000개이다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 지하철 노선의 수를 나타내는 정수 N으로 시작한다. 이어서 N개의 지하철 설명이 주어진다. 각 지하철 설명은 역의 수와 예상 대기 시간(분)을 나타내는 두 정수 $SN_{i}$와 $W_{i}$로 시작한다. 다음 줄은 역 사이의 이동 시간을 설명하는 $SN_{i}$-1개의 정수 $Time_{i,1}$, $Time_{i,2}$, ..., Time_{i,$SN_{i}$-1}로 이루어진다.

지하철 설명 뒤에는 터널의 수를 나타내는 정수 M이 주어진다. 이어지는 M개의 줄에서 터널을 설명한다. 각 터널 설명은 5개의 정수 $m1_{i}$, $s1_{i}$, $m2_{i}$, $s2_{i}$, $t_{i}$로 이루어지며, 이는 터널이 S_{$m1_{i}$,$s1_{i}$}역과 S_{$m2_{i}$,$s2_{i}$}역을 연결한다는 뜻이다. 터널을 걷는 데 걸리는 시간은 $t_{i}$이다.

다음 줄에는 질의의 수를 나타내는 정수 Q가 주어진다. 이어지는 Q개의 각 줄은 4개의 정수 x1, y1, x2, y2로 이루어지며, 이는 $S_{x1,y1}$역에서 $S_{x2,y2}$역으로 이동하려 한다는 뜻이다.

각 테스트 케이스마다 "Case #x:"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이다. 이어서 Q개의 줄을 출력하며, 각 줄에는 해당 질의에 필요한 최단 시간인 정수 y를 출력한다. 이동이 불가능하면 해당 질의에 대해 대신 -1을 출력한다.

첫 번째 테스트 케이스에서는 지하철 1호선의 1역에서 지하철 2호선의 4역으로 이동하려고 한다. 최적의 방법은 다음과 같다:

• 1호선을 타기 위해 3분을 기다린 뒤 승차한다.

• 3분 동안 타고 2역에서 내린다.

• 터널을 이용해 1분 동안 걸어서 2호선의 2역으로 간다.

• 2호선을 타기 위해 2분을 기다린 뒤 승차한다.

• 2분 동안 타고 4역에서 내린다.

총시간은 3+3+1+2+2=11이다.