뱀 JOI

뱀 JOI는 어느 커다란 저택에 길을 잃고 들어왔다. 저택에 사는 사람에게 들키기 전에 저택을 빠져나가야 한다.

이 저택에는 방이 $N$개 있고 $1, 2, \ldots, N$의 번호가 붙어 있다. 복도는 $M$개 있으며 $i$번째 복도($1 \le i \le M$)는 방 $A_i$와 방 $B_i$를 잇는다. JOI는 복도를 양쪽 방향으로 모두 지나갈 수 있고, 복도 $i$를 지나는 데 $D_i$분이 걸린다. 복도를 지나는 것 말고는 방과 방 사이를 이동할 방법이 없다.

저택의 각 방은 온도가 일정하게 맞춰져 있으며, JOI에게는 너무 춥거나, 쾌적하거나, 너무 덥다. JOI는 급격한 온도 변화를 견디지 못하므로 너무 추운 방을 마지막으로 나온 뒤 $X$분이 지나기 전에는 너무 더운 방에 들어갈 수 없다. 마찬가지로 너무 더운 방을 마지막으로 나온 뒤 $X$분이 지나기 전에는 너무 추운 방에 들어갈 수 없다.

JOI는 이동 중에 방에 들어가면 곧바로 그 방을 나와야 한다. 또한 복도 중간에서 되돌아가거나 복도 $i$를 $D_i$분보다 오래 걸려 지날 수도 없다. 단, 이미 방문한 방에 다시 들어가거나 이미 쓴 복도를 다시 쓰는 것은 허용된다.

JOI는 지금 방 $1$에 있으며, 이 방은 JOI에게 너무 춥다. JOI는 저택의 출구가 있는 방 $N$에 들어가면 저택을 빠져나갈 수 있다.

JOI가 저택을 빠져나가는 데 걸리는 최소 시간을 구하시오.

입력은 $1 + N + M$줄로 이루어진다.

첫째 줄에 정수 $N$, $M$, $X$($2 \le N \le 10\,000$, $1 \le M \le 20\,000$, $1 \le X \le 200$)가 공백으로 구분되어 주어진다. 저택에 방이 $N$개, 복도가 $M$개 있고, JOI가 온도 변화에 적응하는 데 $X$분이 걸린다는 뜻이다.

다음 $N$줄 중 $i$번째 줄($1 \le i \le N$)에는 방 $i$의 온도를 나타내는 정수 $T_i$($0 \le T_i \le 2$)가 주어진다. JOI에게 방 $i$는 $T_i = 0$이면 너무 춥고, $T_i = 1$이면 쾌적하며, $T_i = 2$이면 너무 덥다. $T_1 = 0$이 보장된다.

다음 $M$줄 중 $j$번째 줄($1 \le j \le M$)에는 정수 $A_j$, $B_j$, $D_j$($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$)가 공백으로 구분되어 주어진다. 복도 $j$가 방 $A_j$와 방 $B_j$를 잇고, 지나는 데 $D_j$분이 걸린다는 뜻이다. 같은 두 방을 잇는 복도가 여러 개 있을 수 있다.

JOI가 저택을 빠져나갈 수 있는 입력만 주어진다.

JOI가 저택을 빠져나가는 데 걸리는 최소 시간(분)을 정수로 한 줄에 출력한다.

예제 1에서는 방을 $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$ 순서로 이동하는 것이 가장 빠르다.

예제 2에는 같은 두 방(예를 들어 방 $1$과 방 $5$)을 잇는 복도가 여러 개 있다.