JOI, một chú rắn, bị lạc vào một dinh thự rộng lớn. Chú phải thoát ra trước khi bị chủ dinh thự phát hiện.

Dinh thự có \(N\) căn phòng, được đánh số từ \(1\) đến \(N\), và \(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 có thể đi qua mỗi hành lang theo cả hai hướng và cần \(D_i\) phút để đi qua hành lang thứ \(i\). Không có cách nào di chuyển giữa các phòng ngoài việc đi qua hành lang.

Nhiệt độ trong mỗi phòng được giữ cố định và đối với JOI, căn phòng đó hoặc quá lạnh, hoặc dễ chịu, hoặc quá nóng. Vì không thể thích nghi với sự thay đổi nhiệt độ đột ngột, JOI không được bước vào một căn phòng quá nóng khi chưa đủ \(X\) phút kể từ lần gần nhất rời khỏi một căn phòng quá lạnh. Tương tự, JOI không được bước vào một căn phòng quá lạnh khi chưa đủ \(X\) phút kể từ lần gần nhất rời khỏi một căn phòng quá nóng.

Trong lúc di chuyển, ngay sau khi bước vào một căn phòng, JOI phải lập tức rời khỏi căn phòng đó. Chú không được quay lại giữa hành lang hoặc mất nhiều hơn \(D_i\) phút để đi qua hành lang thứ \(i\). Tuy nhiên, JOI được phép bước vào lại một phòng đã từng đến và đi lại qua một hành lang đã từng sử dụng.

Ban đầu JOI đang ở phòng \(1\), một căn phòng quá lạnh. Khi bước vào phòng \(N\), nơi có lối ra, JOI thoát khỏi dinh thự.

Hãy tính thời gian ngắn nhất để JOI 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 thứ nhất chứa ba số nguyên \(N, M, X\). Dinh thự có \(N\) phòng, \(M\) hành lang, và JOI cần \(X\) phút để thích nghi với sự thay đổi nhiệt độ.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(T_i\) mô tả nhiệt độ của phòng \(i\): \(T_i=0\) nếu phòng quá lạnh, \(T_i=1\) nếu phòng dễ chịu, và \(T_i=2\) nếu phòng quá nóng.
• Trong \(M\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(A_j, B_j, D_j\). Hành lang thứ \(j\) nối phòng \(A_j\) với phòng \(B_j\) và cần \(D_j\) phút để đi qua. Có thể có nhiều hành lang nối cùng một cặp phòng.

Dữ liệu ra

In ra một số nguyên trên một dòng: số phút ít nhất để JOI thoát khỏi dinh thự.

Ràng buộc

Các giá trị thỏa mãn:

• \(2 \le N \le 10\,000\).
• \(1 \le M \le 20\,000\).
• \(1 \le X \le 200\).
• \(0 \le T_i \le 2\).
• \(T_1=0\).
• \(1 \le A_j < B_j \le N\).
• \(1 \le D_j \le 200\).

Dữ liệu bảo đảm JOI có thể thoát khỏi dinh thự.

Phân nhóm

Bài có năm bộ dữ liệu chấm, mỗi bộ trị giá \(20\) điểm.

Ví dụ

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

9

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

6

Nguồn

Kỳ thi chọn đội tuyển Olympic Tin học Nhật Bản JOI 2016/2017, vòng sơ khảo, bài 6: Snake JOI.