길 잃은 제리

톰에게 쫒기고 있던 제리가 어느 대저택에 숨었다.

톰을 겨우 따돌렸다고 생각한 제리는 저택을 나와 집으로 갈 작정이다.

그런데 이 저택을 나가는 길을 알 수가 없었다.

이 저택에는 방이 N개 있으며, 1, 2, ..., N의 번호가 매겨져있다.

또한 복도가 M개 있고, i(1 ≦ i ≦ M)번 복도는 방 Ai와 방 Bi를 연결한다.

제리는 이 복도를 어느 방향으로든 지나갈 수 있으며 복도 i를 지나는 데는 Di 분 걸린다.

복도 이외에 방과 방 사이를 이동하는 다른 방법은 없다.

이 저택에 있는 방들의 실내 온도는 각각 일정하게 조절되고 있는데,

제리에게는 너무 춥거나 적당하거나, 너무 더운 온도이다.

제리는 갑작스러운 온도 변화에 적응하지 못한다.

마지막에 너무 추운 방을 나오고 나서 X 분 미만 동안 너무 더운 방에 들어갈 수 없다.

마찬가지로 마지막에 너무 더운 방을 나오고 나서 X 분 미만 동안 너무 추운 방에 들어갈 수 없다.

제리는 이동 중에 방에 들어서자마자 방에서 나와야한다. 방주인에게 들키면 잡히기 때문이다.

또한 복도 중간에 되돌아가거나 복도 i를 Di보다 오래 걸쳐 통과 할 수 없다.

그러나 한 번 방문한 방에 다시 들어가거나, 한번 사용한 복도를 다시 사용하는 것은 허용된다.

제리는 현재 방 1에 있다. 이 방은 제리에게 너무 춥다.

제리는 저택의 출구가 있는 N번 방에 도착하면 집에서 탈출 할 수 있다.

제리가 저택을 탈출하는 데 걸리는 최소 시간을 구하라.

입력 예 1을 보면 방을 1 → 2 → 3 → 4 → 5 → 6 → 5 → 8로 이동하는 것이 최소 시간이다.

입력 예 2는 일부 객실의 쌍 (예를 들어 방 1과 방 5)을 연결하는 복도가 여러 개 있다는 것에 유의하라.

입력

첫 행에 세 정수 N, M, X(2 ≦ N ≦ 10000, 1 ≦ M ≦ 20000, 1 ≦ X ≦ 200) 가 주어진다.

이것은 대저택에 N개의 방과 M개의 복도가 있고 제리가 온도에 적응하는데 X분이 걸린다는 의미이다.

다음 N(1 ≦ i ≦ N)행에 방 i의 온도를 나타내는 정수 Ti (0 ≦ Ti ≦ 2)가 주어진다.

Ti = 0 인 경우 너무 추운 경우를, Ti = 1 인 경우 적당한 온도를, Ti = 2인 경우 더운 경우를 의미한다. T1 = 0 인 것이 보장된다.

다음 M(1 ≦ j ≦ M)개의 행에는 3 개의 정수 Aj, Bj, Dj (1 ≦ Aj < Bj ≦ N, 1 ≦ Dj ≦ 200)가 공백을 구분하여 주어진다.

이것은 복도 j가 방 Aj와 방 Bj를 통과하는데 Dj 분 걸리는 것을 나타낸다.

같은 방 쌍을 연결하는 복도가 여러 개 있을 수 있다는 점에 유의하라.

주어진 입력 데이터에서 제리가 저택을 탈출 할 수 있다는 점이 보장된다.

출력

제리가 저택을 탈출하는 데 최소 몇 분 걸리는지를 나타내는 정수를 한 줄에 출력하라.

예제1

예제2

예제3

예제4

출처

JOI 2017 예선

#3033

길 잃은 제리 2초 512MB

문제

입력

출력

예제1

예제2

예제3

예제4

출처

역링크

#3033 upload 654회 done 215회 how_to_reg 175명

길 잃은 제리 timer 2초 memory 512MB

문제 picture_in_picture_alt text_fields

입력

출력

예제1

예제2

예제3

예제4

출처

역링크

#3033

길 잃은 제리 2초 512MB

문제