무기 시장

미국은 $1 \ldots N$번으로 번호가 매겨진 $N$개의 주(state)로 이루어져 있다. 유스(Juss)의 집은 $N$번 주에 있다. 그곳에서는 한 남자가 총기를 얼마나 많이 가지고 있는지로 그 사람의 담대함을 평가하는 관습이 있다. 유스는 담대한 사람이 되고 싶어서 올해 $1$번 주에서 열리는 첨단 총기 시장을 방문하기로 결심했다.

유스에게 다행히도 $1$번 주에서는 마침 "애국적 자기방어법"이 통과되어, 개인이 총기 시장에서 구입한 모든 총기의 값을 주 정부가 부담해 준다. 따라서 유스는 원하는 만큼 많은 총기를 구할 수 있다.

그러나 여러 세계적 위기 때문에 휘발유가 매우 비싸서, 유스는 돌아오는 길에 쓸 휘발유를 $K$ 단위밖에 구할 수 없다. 주들은 $M$개의 양방향 고속도로로 연결되어 있으며, 휘발유 $1$ 단위로 $1$ km의 거리를 이동할 수 있다. 두 주가 두 개 이상의 고속도로로 연결되어 있을 수도 있다.

또한 모든 주가 자기 주의 거리에서 수백만 정의 총기를 보고 싶어 하는 것은 아니다. 그래서 주마다 한 사람이 지니고 다닐 수 있는 총기 수에 대한 제한이 다르다. $i$번 주에서 개인은 최대 $C_i$정의 총기를 지니고 다닐 수 있다.

제한된 휘발유의 양과 지나가는 주들의 총기 운반 제한을 모두 고려할 때, 유스가 집으로 가져갈 수 있는 총기의 최대 개수를 구하라.

첫째 줄에 세 정수 $N$, $M$, $K$ ($2 \le N \le 10^5$, $1 \le M \le 10^5$, $1 \le K \le 10^9$)가 주어진다. 각각 주의 개수, 고속도로의 개수, 그리고 돌아오는 길을 위해 살 수 있는 휘발유의 양을 나타낸다.

둘째 줄에는 공백으로 구분된 $N$개의 정수 $c_i$ ($-1 \le c_i \le 10^9$)가 주어진다. $c_i$는 $i$번 주에서 지니고 다닐 수 있는 총기 수의 제한을 나타내며, $c_i = -1$이면 제한이 없다는 뜻이다. $1$번 주와 $N$번 주에는 제한이 없다고 가정해도 된다.

이어지는 $M$개의 줄에는 각각 세 정수 $A_i$, $B_i$, $L_i$ ($1 \le L_i \le 10^9$)가 주어진다. 이는 $A_i$번 주와 $B_i$번 주가 길이 $L_i$ km인 고속도로로 연결되어 있음을 뜻한다. $K$ 단위의 휘발유로 유스가 집까지 갈 수 있음이 보장된다.

유스가 집으로 가져갈 수 있는 총기의 최대 개수를 정수 하나로 한 줄에 출력한다. 만약 유스가 제한 없이 총기를 가져갈 수 있다면 $-1$을 출력한다.