우체국 점검

이 나라로 들어오는 국제 우편은 모두 중앙 우체국에 먼저 모인다. 그다음 여러 우체국을 거쳐 목적지 우체국까지 전달된다. 배달 경로는 방향 그래프 $G = (V, E)$로 나타낸다. $V$는 우체국의 집합이고, $E$는 우편을 넘길 수 있는 구간의 집합이다. 운영이 효율적이지 않아서 우편이 항상 최단 경로로 가지는 않는다.

우체국은 몇 개의 그룹으로 나뉜다. 그룹은 어느 우체국에서 그룹 안의 다른 어느 우체국으로도 직접 또는 다른 우체국을 거쳐 우편을 보낼 수 있는 우체국의 집합이다. 한 그룹에 속한 우체국은 10개를 넘지 않는다.

우편이 아직 오지 않았다는 민원이 자주 들어온다. 원인은 대개 우체국 한 곳의 시스템 장애지만 그곳을 찾아내기가 쉽지 않다. 그래서 민원이 들어오면 고객 지원팀은 후보 우체국마다 직원을 보내 시스템을 점검한다. 우체국 $u$를 점검하는 비용은 $c_u$이고, 이 값은 우체국 규모에 따라 다르다.

나라 안에 우체국이 많고 민원도 자주 들어오므로 우정 당국은 점검 비용을 줄이려 한다. 그래서 다음 규칙을 쓴다. 하루 동안 우체국 $w_1, \dots, w_k$에서 민원이 들어오면, 다음 날 후보 중 점검 비용이 가장 작은 우체국 $v$ 한 곳에만 직원을 보낸다. 중앙 우체국에서 $w_1, \dots, w_k$ 각각으로 가는 모든 경로가 반드시 $v$를 지나면 우체국 $v$는 후보다. $v$에서 문제를 찾지 못하면 나머지 우체국을 점검하는 순서를 정해야 하지만, 그 일은 나중으로 미루며 이 문제에서 다루지 않는다.

중앙 우체국에서 $w$로 가는 경로는 우체국 1에서 시작해 우체국 $w$에서 끝나므로, 두 우체국도 경로가 지나는 우체국에 든다.

하루치 민원 우체국 목록이 질의로 주어질 때, 후보 중 가장 낮은 점검 비용을 출력한다.

입력은 테스트 케이스 하나로 이루어지며, 형식은 다음과 같다.

n m
u_1 v_1
...
u_m v_m
c_1
...
c_n
q
k_1 w_1,1 ... w_1,k_1
...
k_q w_q,1 ... w_q,k_q

$n$은 우체국의 수($2 \le n \le 50\,000$)이고, 우체국에는 1부터 $n$까지 번호가 붙어 있다. 우체국 1이 중앙 우체국이다. $m$은 전달 구간의 수($1 \le m \le 100\,000$)다. 구간 $u_i$, $v_i$는 우체국 $u_i$가 받은 우편 가운데 일부를 우체국 $v_i$로 넘긴다는 뜻이다. $c_j$는 우체국 $j$의 점검 비용($1 \le c_j \le 10^9$)이다. $q$는 질의의 수($q \ge 1$)이고, 각 질의는 미배달 민원이 들어온 우체국의 목록이다. $k_i$는 $i$번째 목록의 길이($k_i \ge 1$)이고, $w_{i,1}, \dots, w_{i,k_i}$는 서로 다른 우체국이다. 모든 질의의 $k_i$를 더한 값은 $50\,000$ 이하다.

중앙 우체국에서 모든 우체국으로 가는 배달 경로가 적어도 하나씩 있다. 서로 오갈 수 있는 우체국 그룹의 크기는 10을 넘지 않는다.

각 질의마다 후보 중 가장 낮은 점검 비용을 한 줄에 하나씩 출력한다.