Trong khu rừng nơi chú sóc bay đường JOI sinh sống có \(N\) cây bạch đàn, được đánh số từ \(1\) đến \(N\). Cây \(i\) cao \(H_i\) mét.

Có \(M\) cặp cây mà JOI có thể bay trực tiếp từ cây này sang cây kia theo cả hai chiều. Với mỗi cặp, thời gian cần để bay giữa hai cây đã được xác định. Trong lúc bay, độ cao của JOI so với mặt đất giảm \(1\) mét mỗi giây. Cụ thể, nếu độ cao hiện tại là \(h\) mét và chuyến bay mất \(t\) giây thì khi đến nơi, độ cao của JOI sẽ là \(h-t\) mét. Tuy nhiên, JOI không thể thực hiện chuyến bay nếu \(h-t < 0\) hoặc \(h-t\) lớn hơn chiều cao của cây đích.

Ngoài ra, JOI có thể di chuyển lên hoặc xuống dọc theo thân cây đang đứng, thay đổi độ cao trong khoảng từ \(0\) mét đến chiều cao của cây đó. Mỗi lần tăng hoặc giảm độ cao \(1\) mét mất \(1\) giây.

JOI muốn đi từ vị trí ở độ cao \(X\) mét trên cây \(1\) đến ngọn cây \(N\), tức vị trí ở độ cao \(H_N\) mét, và muốn biết thời gian ít nhất cần để thực hiện việc này.

Yêu cầu

Cho chiều cao của từng cây, thông tin về các cặp cây JOI có thể bay trực tiếp giữa chúng và độ cao ban đầu của JOI. Hãy tính thời gian ít nhất để JOI đến ngọn cây \(N\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(N, M, X\) cách nhau bởi dấu cách. Có \(N\) cây, \(M\) cặp cây có thể bay trực tiếp giữa chúng, và ban đầu JOI ở độ cao \(X\) mét trên cây \(1\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa số nguyên \(H_i\), là chiều cao tính bằng mét của cây \(i\), với \(1 \le i \le N\).
• Dòng thứ \(j\) trong \(M\) dòng tiếp theo chứa ba số nguyên \(A_j, B_j, T_j\) cách nhau bởi dấu cách. JOI có thể bay trực tiếp giữa cây \(A_j\) và cây \(B_j\) theo cả hai chiều, mỗi chuyến mất \(T_j\) giây. Các chỉ số thỏa mãn \(1 \le A_j, B_j \le N\) và \(A_j \ne B_j\). Không có cặp cây nào được liệt kê hai lần: với \(1 \le j < k \le M\), ta có cả \((A_j,B_j) \ne (A_k,B_k)\) và \((A_j,B_j) \ne (B_k,A_k)\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên: thời gian ít nhất, tính bằng giây, để JOI đi từ độ cao \(X\) mét trên cây \(1\) đến ngọn cây \(N\). Nếu không có cách đi như vậy, in ra \(-1\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le M \le 300\,000\).
• \(1 \le H_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• \(1 \le T_j \le 1\,000\,000\,000\) với \(1 \le j \le M\).
• \(0 \le X \le H_1\).

Phân nhóm

• Nhóm 1 (25 điểm): \(N \le 1\,000\), \(M \le 3\,000\), \(H_i \le 100\) với mọi \(1 \le i \le N\), và \(T_j \le 100\) với mọi \(1 \le j \le M\).
• Nhóm 2 (25 điểm): \(X = 0\).
• Nhóm 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20

110

2 1 0
1
1
1 2 100

-1

4 3 30
50
10
20
50
1 2 10
2 3 10
3 4 10

100