HD vừa sáng tạo ra một trò chơi điều khiển robot mới cho 2 bé Bi, Bo chơi. Nội dung trò chơi như sau :

- Có N cây cột đánh số từ 1 đến N, cây cột thứ i có chiều cao h[i](m)

- Có M đường nhảy dạng i, j, t tương ứng là nhảy từ cột i sang cột j (hoặc từ cột j sang cột i) mất t(s) và nếu nhảy từ độ cao h (h <= h[i]) của cây i sang cây j thì sẽ có độ cao là h - t với điều kiện 0 <= h - t <= h[j].

- Nếu robot di chuyển lên xuống trên cột hiện tại, thời gian di chuyển mất 1(s) trên 1m di chuyển.

Hiện tại robot đang ở độ cao X của cây 1, Bi-Bo cần phải tìm phương án di chuyển nhanh nhất đến độ cao h[N] của cây N. Bạn hãy giúp 2 bé Bi-Bo tính thời gian di chuyển ngắn nhất thỏa mãn yêu cầu trên.

Input

- Dòng 1 : Chứa 3 số nguyên dương N, M, X. (2 <= N <= 100.000; 1 <= M <= 300.000; 0 <= X <= h[1])

- N dòng tiếp theo, dòng thứ i là h[i] (h[i] <= 10^9)

- M dòng tiếp theo là 3 số i, j, t tương ứng là nhảy từ cây i sang cây j (hoặc j sang i) mất t(s) (1 <= t <= 10^9)

Output

- Ghi ra 1 số duy nhất là thời gian ngắn nhất để di chuyển từ độ cao X của cột 1 đến độ cao h[N] của cột N, nếu không có đáp án in -1.

Example

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

Output:
110

Giới hạn :

- 25% số điểm tương ứng với các test có : N <= 1.000; M <= 3.000; h[i] <= 100; t <= 100

- 25% số điểm tương ứng với X = 0.