직장인 파댕이의 사회생활

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

요약

모든 층이 같은 건물에서 1층 1번 방부터 K층 N번 방까지 가는 최소 시간을 구합니다. 복도와 엘리베이터를 함께 사용합니다.

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

문제

파댕이는 중견기업에서 직장인으로 일하고 있다. 사장님이 파댕이를 무척 아끼기 때문에, 파댕이는 사장실에 찾아가 사장님께 인사하려고 한다.

파댕이가 다니는 회사 건물은 $K$ 층으로 되어 있다. 각 층은 방과 복도로 이루어져 있다. 복도를 통해 방과 방 사이를 양방향으로 이동할 수 있다. 모든 층은 같은 모습이다. 파댕이는 지금 $1$ 층의 $1$ 번 방에 있고, 사장실은 $K$ 층의 $N$ 번 방이다. 파댕이가 사장실에 가장 짧은 시간에 도착하는 방법을 찾아야 한다.

파댕이는 복도를 하나 지나가는 데 걸리는 시간을 알고 있다. 방 중에는 엘리베이터가 있어서 위층으로 올라갈 수 있는 곳도 있다. $i$ 번 방의 엘리베이터는 다른 모든 층의 $i$ 번 방과 연결된다. 특정 엘리베이터에만 사람이 몰리기 때문에 엘리베이터마다 빠르기가 다르다. 파댕이는 각 엘리베이터가 한 층을 올라가는 데 걸리는 시간도 알고 있다.

건물의 모습과 엘리베이터의 속도가 주어졌을 때, 파댕이가 사장실까지 가는 최소 시간을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 방의 수 $N (2 \leq N \leq 100,000)$ , 복도의 수 $M (1 \leq M \leq 300,000)$ , 건물의 층수 $K (2 \leq K \leq 200,000)$ 가 공백으로 구분되어 주어진다.

다음 $M$ 개의 줄에는 세 정수 $u$ , $v$ , $c$ 가 공백으로 구분되어 주어진다. $(1 \leq u, v \leq N, 1 \leq c \leq 100,000,000, u \neq v)$ 이는 $u$ 번 방과 $v$ 번 방을 잇는 복도가 있으며, 이를 지나가는 데 걸리는 시간이 $c$ 라는 뜻이다.

서로 다른 두 방을 잇는 복도는 최대 1개이다.

다음 줄에는 $N$ 개의 정수 $e\_1, \cdots, e\_N$ 이 공백으로 구분되어 주어진다. $(e\_i = -1 \mbox{ or } 1 \leq e\_i \leq 100,000,000)$ 이는 $i$ 번 방에 있는 엘리베이터를 타면 한 층을 올라갈 때마다 $e\_i$ 의 시간이 든다는 뜻이다. $i$ 번 방에 엘리베이터가 없다면 $e\_i = -1$ 이다.

출력

파댕이가 사장실까지 가는 최소 시간을 출력한다. 파댕이가 사장실에 도달할 수 없다면 $-1$ 을 출력한다.

예제2

예제 1

입력

5 7 4
1 2 7
1 3 11
1 4 7
2 3 13
2 4 4
2 5 16
4 5 10
3 -1 1 3 -1

예상 출력

예제 2
입력
```
3 2 7
1 2 3
2 3 8
-1 -1 -1
```
예상 출력
```
-1
```