Đổ xăng

Có $n$ thành phố đánh số từ $1$ đến $n$ và $m$ con đường hai chiều. Con đường thứ $i$ nối hai thành phố $u_i$, $v_i$ và có độ dài $d_i$: đi hết con đường này tốn đúng $d_i$ lít xăng. Có thể có đường nối một thành phố với chính nó và nhiều đường nối cùng một cặp thành phố.

Bạn lái một chiếc xe có bình xăng chứa tối đa $C$ lít, xuất phát ở thành phố $1$ với bình rỗng và muốn tới thành phố $n$. Ở thành phố $v$ có trạm xăng bán với giá $p_v$ cho mỗi lít; tại đó bạn được mua một số nguyên lít bất kỳ, miễn là lượng xăng trong bình không vượt quá $C$. Xe chỉ đi vào một con đường khi trong bình có ít nhất $d_i$ lít.

Hãy tính số tiền ít nhất cần bỏ ra để tới thành phố $n$.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $n$, $m$, $C$.
• Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\dots ,p_n$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $u_i,v_i,d_i$.

Dữ liệu ra

In ra số tiền ít nhất, hoặc $-1$ nếu không thể tới thành phố $n$.

Ràng buộc

• $1\le n\le 1000$
• $0\le m\le 4000$
• $1\le C\le 100$
• $1\le p_v\le {10}^6$
• $1\le u_i,v_i\le n$
• $1\le d_i\le 100$

Ví dụ