31588번 - Alternative Mart

민식이는 OJUZ 시에서 자취하고 있다. OJUZ 시는 $N$개의 지역과 $M$개의 양방향 도로로 이루어져 있으며 $N$개의 지역 중 $K$개의 지역에는 할인마트가 위치해있다. 지역의 번호는 $1$ 이상 $N$ 이하의 정수이며 특정한 두 지역을 직접 연결하는 도로는 최대 하나 있으며 모든 도로의 두 끝 지역은 다르다. 또한 임의의 지역에서 다른 지역으로 가는 방법이 항상 존재한다.

민식이는 자기 일과가 끝나면 할인마트로 가서 요리재료와 간식거리를 산 후 자취방에 돌아온다. 민식이는 꽤 똑똑하기 때문에 항상 가장 빠른 길로 할인마트에 가서 물건을 산다. 허나, 어떤 경우에는 몇 개의 할인마트가 문을 닫을 때가 있다. 할인마트가 문을 닫으면 기존에 민식이가 가던 방법이 무용지물이 될 수 있다. 민식이는 자신이 자주 가던 할인마트가 문을 닫으면 어떤 할인마트로 가야 하는지 몰라 난감해한다.

민식이를 도와 매 순간 어떤 할인마트로 가야 하는지 구하는 프로그램을 작성하여라. 단, 민식이가 할인마트에서 집까지 가는 시간은 무시한다.

첫 번째 줄에는 지역의 수 $N$, 도로의 수 $M$, 할인마트의 수 $K$, 질의의 수 $Q$가 주어진다. ($2 \le N \le 50\,000$, $N−1 \le M \le 80\,000$, $1 \le K \le N$, $1 \le Q \le 50\,000$)

두 번째 줄에는 $K$개의 할인마트들이 위치한 지역의 번호가 오름차순으로 주어진다.

세 번째 줄부터 $M$개의 줄에는 도로의 두 끝점 $P_i$, $Q_i$와 도로의 길이 $V_i$가 주어진다. ($1 \le P_i, Q_i \le N$, $1 \le V_i \le 10\,000$)

$M+3$번째 줄부터 $Q$개의 줄에는 민식이의 질의가 주어진다.

각 질의별로 민식이의 출발 지역 $S$와 문을 닫는 할인마트의 수 $X$, 그리고 문을 닫는 할인마트가 있는 지역의 번호 $C_1$, …, $C_X$가 주어진다. ($0 \le X \le min(10, K−1)$, $1 \le S, C_i \le N$)

$Q$개의 줄에 걸쳐, 민식이가 가야 하는 할인마트의 번호(할인마트가 위치한 지역의 번호)와 그때 민식이가 할인마트를 가는 최소 시간을 출력한다.

가장 빨리 갈 수 있는 할인마트가 여러 개라면 번호가 가장 작은 것을 출력한다.