문제

뱀인 JOI 군은 어느 큰 저택에 잘못 들어가고 말았다. 저택의 거주자에게 들키기 전에 저택을 탈출해야 한다.

이 저택에는 방이 $N$개 있으며, $1, 2, \dots, 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$줄로 이루어진다.

$1$번째 줄에는 $3$개의 정수 $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $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$)에는 $3$개의 정수 $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

8 10 4
0
1
1
2
1
1
2
0
1 2 1
1 3 1
2 3 3
2 4 5
3 4 1
4 5 1
5 6 1
5 8 1
1 7 2
7 8 2

출력 예 1

9

입력 예 2

15 25 4
0
1
1
0
2
1
0
1
1
2
0
0
1
0
1
8 11 1
7 10 1
12 14 1
3 8 1
1 5 1
3 9 1
3 8 1
1 5 1
6 15 1
11 12 1
2 14 1
7 10 1
11 12 1
5 13 1
2 8 1
1 4 1
2 11 1
5 6 1
1 13 1
6 12 1
5 10 1
9 13 1
4 10 1
3 12 1
7 13 1

출력 예 2

6

입력 예 1에서는 방을 $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$의 순서로 이동하는 것이 최단이 된다.

입력 예 2에서는 몇몇 방의 쌍(예를 들어 방 $1$과 방 $5$)을 연결하는 복도가 여러 개 있다.