출구가 바뀌는 미궁

면접 대비

시간 제한1초메모리 제한1024 MB

요약

형진이 1번 정점에서 출발해 열려 있는 출구로 탈출하는 가장 짧은 시간을 구합니다. 출구는 K초마다 순서대로 열리고 닫힙니다.

난이도: 보통10점 중 5점
유형: 그래프, 최단 경로, 수학
정답자: 아직 제출이 없습니다

문제

형진이는 $K$ 초마다 열려 있는 출구가 바뀌는 이상한 미궁에 들어오게 되었다.

$0$ 초부터 $K-1$ 초까지 첫 번째 출구가 열린다. 나머지 출구는 닫힌다.
$K$ 초부터 $2K-1$ 초까지 두 번째 출구가 열린다. 나머지 출구는 닫힌다.
$2K$ 초부터 $3K-1$ 초까지 세 번째 출구가 열린다. 나머지 출구는 닫힌다.
이렇게 $K$ 초마다 출구가 열리고 닫히는 것이 반복된다.

미궁은 $1$ 번 정점부터 $N$ 번 정점까지 $N$ 개의 정점과 $M$ 개의 양방향 간선으로 구성되어 있다. 형진이는 간선을 따라 연결된 다른 정점으로 이동할 수 있다.

미궁에는 출구가 총 $X$ 개 있으며, 각각 $E_1, E_2, \dots, E_X$ 번 출구이다. $i$ 번째 출구는 다음 규칙에 따라 열리고 닫힌다.

$1 \le i \le X$ 이면 $E_i$ 번 출구가 열린다.
$i > X$ 이면 $i-X$ 번째로 열렸던 출구와 같은 출구가 열린다.

형진이는 미궁의 구조와 출구 정보를 알고 있다. 그는 $0$ 초에 $1$ 번 정점에서 출발해 열려 있는 출구로 미궁을 탈출하려고 한다. 형진이는 전략적이어서 특정 정점에서 잠시 멈춰 쉴 수 있다. 출구가 있는 정점에서 그 출구로 나가는 데는 시간이 걸리지 않는다. 형진이가 가능한 한 빨리 탈출했을 때 걸리는 시간을 구하라.

입력

첫 번째 줄에 미궁 정점의 개수 $N$ , 간선의 개수 $M$ , 출구가 바뀌는 시간 $K$ 가 주어진다. ( $3 \le N, M \le 200\,000$ , $1 \le K \le 10^9$ )

다음 $M$ 개의 줄에는 간선 정보 $a_i$ , $b_i$ , $c_i$ 가 주어진다. 이는 $a_i$ 번 정점과 $b_i$ 번 정점이 간선으로 이어져 있고, 그 간선을 지나는 데 $c_i$ 초가 걸린다는 뜻이다. ( $1 \le a_i, b_i \le N$ , $a_i \ne b_i$ , $1 \le c_i \le 10^9$ )

다음 줄에 출구가 바뀌는 개수 $X$ 가 주어진다. ( $1 \le X \le N$ )

다음 줄에 출구 정보 $E_1, E_2, \dots, E_X$ 가 공백으로 구분되어 주어진다. ( $1 \le E_i \le N$ , 모든 $E_i$ 는 서로 다르다.)

주어지는 그래프는 연결 그래프이며, 임의의 두 정점 사이에 간선은 최대 1개 있다.

출력

첫 번째 줄에 열려 있는 출구를 통해 가장 빠르게 탈출했을 때 걸리는 시간을 출력한다.

예제2

예제 1
입력
```
4 3 15
1 2 5
2 3 10
3 4 20
2
3 4
```
예상 출력
```
30
```
예제 2
입력
```
4 3 15
1 2 5
2 3 10
3 4 10
2
3 4
```
예상 출력
```
25
```