30985번 - 직장인 파댕이의 사회생활

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

직장인 파댕이의 회사가 있는 건물은 $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$을 출력한다.