Đề bài

Chú rắn JOI-kun đã đi lạc vào một dinh thự rộng lớn. Trước khi bị người sống trong dinh thự phát hiện, cậu phải thoát ra khỏi dinh thự này.

Trong dinh thự có $N$ căn phòng, được đánh số $1, 2, \dots, N$. Ngoài ra còn có $M$ hành lang, hành lang thứ $i$ ($1 \le i \le M$) nối phòng $A_i$ với phòng $B_i$. JOI-kun có thể đi qua các hành lang này theo cả hai chiều, và mất $D_i$ phút để đi hết hành lang $i$. Không có cách nào để di chuyển giữa các phòng ngoài việc đi qua các hành lang.

Nhiệt độ của mỗi phòng trong dinh thự đều được điều chỉnh ở mức cố định; đối với JOI-kun thì mỗi phòng hoặc là quá lạnh, hoặc là dễ chịu, hoặc là quá nóng. Vì không thể thích ứng với sự thay đổi nhiệt độ đột ngột, JOI-kun không thể đi vào một phòng quá nóng khi chưa đủ $X$ phút kể từ lần cuối cùng rời khỏi một phòng quá lạnh. Tương tự, cậu cũng không thể đi vào một phòng quá lạnh khi chưa đủ $X$ phút kể từ lần cuối cùng rời khỏi một phòng quá nóng.

Trong quá trình di chuyển, ngay khi vừa vào một phòng, JOI-kun phải rời khỏi phòng đó ngay lập tức. Ngoài ra, cậu không thể quay đầu lại ở giữa hành lang, cũng không thể đi qua hành lang $i$ lâu hơn $D_i$ phút. Tuy nhiên, cậu được phép quay lại một phòng đã từng ghé qua hoặc sử dụng lại một hành lang đã từng đi.

Hiện tại JOI-kun đang ở phòng $1$. Căn phòng này quá lạnh đối với JOI-kun. Ngay khi đi vào phòng $N$ — nơi có lối ra của dinh thự — JOI-kun sẽ thoát được khỏi dinh thự.

Hãy tìm thời gian ngắn nhất để JOI-kun thoát khỏi dinh thự.

Dữ liệu vào

Dữ liệu vào gồm $1 + N + M$ dòng.

Ở dòng $1$, ghi $3$ số nguyên $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$) cách nhau bởi khoảng trắng. Điều này cho biết dinh thự có $N$ phòng và $M$ hành lang, đồng thời JOI-kun cần $X$ phút để thích ứng với sự thay đổi nhiệt độ.

Ở dòng thứ $i$ ($1 \le i \le N$) trong $N$ dòng tiếp theo, ghi số nguyên $T_i$ ($0 \le T_i \le 2$) biểu thị nhiệt độ của phòng $i$. Đối với JOI-kun, phòng $i$ là quá lạnh khi $T_i = 0$, dễ chịu khi $T_i = 1$, và quá nóng khi $T_i = 2$. Đảm bảo rằng $T_1 = 0$.

Ở dòng thứ $j$ ($1 \le j \le M$) trong $M$ dòng tiếp theo, ghi $3$ số nguyên $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$) cách nhau bởi khoảng trắng. Điều này cho biết hành lang $j$ nối phòng $A_j$ với phòng $B_j$, và mất $D_j$ phút để đi qua. Lưu ý rằng có thể có nhiều hành lang cùng nối một cặp phòng.

Trong dữ liệu vào đã cho, đảm bảo rằng JOI-kun có thể thoát khỏi dinh thự.

Kết quả

In ra trên $1$ dòng một số nguyên biểu thị số phút ít nhất để JOI-kun thoát khỏi dinh thự.

Ví dụ

Ví dụ 1 - Dữ liệu vào

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

Ví dụ 1 - Kết quả

9

Ví dụ 2 - Dữ liệu vào

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

Ví dụ 2 - Kết quả

6

Trong Ví dụ 1, di chuyển qua các phòng theo thứ tự $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$ là nhanh nhất.

Trong Ví dụ 2, có một số cặp phòng (chẳng hạn như phòng $1$ và phòng $5$) được nối với nhau bởi nhiều hành lang.