뱀 JOI 군

문제

뱀인 JOI 군은, 어떤 커다란 저택에 잘못 들어와 버렸다. 저택의 주민에게 발견되기 전에, 저택을 탈출해야 한다.

이 저택에는 방이 N 개 있고, 1, 2, ..., N 의 번호가 붙어 있다. 또한, 복도가 M 개 있고, i 번째 복도 (1 ≦ i ≦ 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 ≦ N ≦ 10000, 1 ≦ M ≦ 20000, 1 ≦ X ≦ 200) 가 공백으로 구분되어 적혀 있다. 이는, 저택에 N 개의 방과 M 개의 복도가 있고, JOI 군이 온도 변화에 대응하는 데 X 분이 걸림을 나타낸다.

이어지는 N 줄 중 i 번째 줄 (1 ≦ i ≦ N) 에는, 방 i 의 온도를 나타내는 정수 $T_{i}$ (0 ≦ $T_{i}$ ≦ 2) 가 적혀 있다. JOI 군에게 방 i 는, $T_{i}$ = 0 일 때 너무 춥고, $T_{i}$ = 1 일 때 쾌적하며, $T_{i}$ = 2 일 때 너무 덥다. $T_{1}$ = 0 임이 보장된다.

이어지는 M 줄 중 j 번째 줄 (1 ≦ j ≦ M) 에는, 3 개의 정수 $A_{j}$, $B_{j}$, $D_{j}$ (1 ≦ $A_{j}$ < $B_{j}$ ≦ N, 1 ≦ $D_{j}$ ≦ 200) 가 공백으로 구분되어 적혀 있다. 이는, 복도 j 가 방 $A_{j}$ 와 방 $B_{j}$ 를 잇고 있으며, 지나는 데 $D_{j}$ 분이 걸림을 나타낸다. 같은 방의 쌍을 잇는 복도가 여러 개 있을 수 있음에 주의하시오.

주어지는 입력 데이터에서는, JOI 군이 저택에서 탈출할 수 있음이 보장된다.

출력

JOI 군이 저택에서 탈출하는 데 최단으로 몇 분이 걸리는지를 나타내는 정수를 한 줄에 출력한다.

예제 입력 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

예제 1 에서는, 방을 1 → 2 → 3 → 4 → 5 → 6 → 5 → 8 의 순서로 이동하는 것이 최단이다.

예제 입력 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

예제 2 에서는, 몇몇 방의 쌍 (예를 들어 방 1 과 방 5) 을 잇는 복도가 여러 개 있다.