투표 도시

위대한 황제 Lord Pooty가 은퇴를 결심하고, 많은 아들 중 한 명에게 왕관을 넘기려 합니다. 민주주의의 정신에 따라 투표로 후계자를 정하기로 했습니다.

왕국에는 0부터 $N - 1$까지 번호가 붙은 $N$개의 도시가 있습니다. 이 가운데 $K$개는 투표 도시이며, $i$번째 투표 도시는 $T_i$입니다.

시민으로서 여러분은 지정된 투표 도시 중 한 곳으로 이동해 투표합니다. 도로는 $E$개이며, $j$번째 도로는 도시 $U_j$에서 도시 $V_j$로 한 방향으로 이어지고 통행료는 $C_j$입니다. 지역 도시들은 이동 비용을 줄이기 위해 티켓 제도를 열었습니다.

티켓은 1번부터 5번까지 다섯 종류가 있습니다. $x$번 티켓을 사용하면 해당 도로의 통행료가 $(10x)\%$ 줄어듭니다. 즉, 그 티켓을 쓰면 통행료가 $\left(1 - \frac{x}{10}\right)$배가 됩니다.

티켓에는 규칙이 있습니다. 한 도로에 티켓을 두 장 이상 겹쳐 쓸 수 없습니다. 여정을 시작할 때 종류별로 최대 한 장만 살 수 있습니다. 예를 들어 1번 티켓 한 장과 2번 티켓 한 장은 살 수 있지만, 2번 티켓 두 장은 살 수 없습니다. 이는 티켓을 사재기하지 못하게 하려는 것입니다. 티켓은 여정 시작 시점에만 살 수 있습니다.

여러분은 바빠서 출발 도시와 티켓 가격을 미리 알지 못합니다. 출발 도시 $S$와 1번부터 5번까지 티켓 가격 $P_1$부터 $P_5$로 이루어진 상황을 $Q$개 정리했습니다. 티켓을 구할 수 없을 수도 있으며, 이때 가격은 $-1$입니다.

각 상황에서 도로로 도달할 수 있는 투표 도시 중 가장 적은 비용을 구하세요. 모든 도시가 서로 도달할 수 있는 것은 아니므로 걸어가야 할 수도 있습니다.

첫 줄에 정수 $N$, $E$, $K$가 차례로 주어집니다. 각각 도시 수, 도로 수, 투표 도시 수입니다. 둘째 줄에는 $K$개의 정수가 주어지며, $i$번째 값이 투표 도시 $T_i$입니다.

이어지는 $E$개의 줄에는 정수 세 개 $U_j$, $V_j$, $C_j$가 주어집니다. 이는 $U_j$에서 $V_j$로 가는 일방통행 도로이며 통행료는 $C_j$입니다.

다음 줄에는 상황의 수 $Q$가 주어집니다. 이어지는 $Q$개의 줄에는 정수 여섯 개 $S$, $P_1$, $P_2$, $P_3$, $P_4$, $P_5$가 주어집니다. $S$는 출발 도시이고, $P_x$는 $x$번 티켓의 가격입니다.

프로그램은 표준 입력에서 읽어야 합니다.

$Q$개의 줄에 상황마다 정수 하나씩을 입력 순서대로 출력합니다. 각 정수는 해당 상황에서 투표 도시에 이르는 최소 비용입니다. 출발 도시에서 어떤 투표 도시에도 도달할 수 없으면 $-1$을 출력합니다.

프로그램은 표준 출력에 씁니다.

• $1 \le N \le 5000$
• $0 \le E \le 10000$
• $1 \le Q \le 100$
• $0 \le K \le N$
• 모든 $1 \le i \le K$에 대해 $0 \le T_i < N$
• 모든 $1 \le i < j \le K$에 대해 $T_i \ne T_j$
• 모든 $1 \le i \le E$에 대해 $1 \le C_i \le 10^9$
• 모든 $1 \le i \le E$에 대해 $C_i$는 $10$의 배수
• 모든 $1 \le i \le E$에 대해 $0 \le U_i, V_i < N$이고 $U_i \ne V_i$
• 모든 $1 \le i \le 5$에 대해 $-1 \le P_i \le 10^9$