출구가 바뀌는 미궁

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

요약

출구가 주기 K로 번갈아 열리는 가중 무방향 그래프에서 1번 정점에서 출발해 가장 빨리 탈출하는 시간을 구한다.

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

문제

형진이는 $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 \gt 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 \neq 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
```