최단 경로들

Nikola는 Bit 마을에 살고, Hex 마을에 사는 Anita와 사귀고 있다. Nikola는 주변 지도를 훤히 알고 있어서 두 마을을 잇는 최단 경로 하나를 찾아 두었고, 이 경로를 ‘행운의 경로’라고 부른다. 지도는 서로 다른 마을들을 잇는 양방향 도로들의 집합으로 주어진다.

어느 날 대통령이 도로 공사를 하기로 했다. 나라의 교통을 유지하기 위해 하루에 도로를 딱 하나만 닫는다.

행운의 경로 위에 있는 각 도로에 대해, 그 도로가 닫혔을 때 Nikola의 마을에서 Anita의 마을까지 가는 최단 경로의 길이를 구하라.

첫째 줄에 네 정수 $n$, $m$, $a$, $b$가 주어진다. $n$은 마을의 수, $m$은 도로의 수, $a$는 Nikola가 사는 Bit 마을의 번호, $b$는 Anita가 사는 Hex 마을의 번호이다.

마을에는 $1$부터 $n$까지 번호가 매겨져 있다. 이어지는 $m$개의 줄에는 각각 세 정수 $u$, $v$, $w$가 주어지며, 마을 $u$와 마을 $v$가 길이 $w$인 도로로 연결되어 있음을 뜻한다.

마지막 줄에는 정수 $k$와 $k$개의 마을 번호 $v_1, v_2, \ldots, v_k$가 주어진다($v_1 = a$, $v_k = b$). 이는 Nikola의 행운의 경로를 나타낸다.

각 $t = 1, 2, \ldots, k-1$에 대해 한 줄씩, 도로 $(v_t, v_{t+1})$이 닫혔을 때 마을 $a$에서 마을 $b$까지의 최단 경로 길이를 출력한다. 경로가 존재하지 않으면 $-1$을 출력한다.

• $1 \le n \le 2000$, $1 \le m \le 100000$
• $1 \le a, b \le n$
• $1 \le w \le 100000$
• 서로 다른 두 마을 사이에는 도로가 최대 하나 존재한다.
• 주어지는 행운의 경로는 마을 $a$에서 마을 $b$까지의 최단 경로 중 하나이다.