The Firearms Market

The United States consists of $N$ states, numbered $1 \ldots N$. Juss's home is in state $N$. There it is customary to judge a man's toughness by how many firearms he owns. Juss wants to be a tough man, so he decided to visit this year's high-tech firearms market held in state $1$.

Luckily for Juss, state $1$ has just passed a "patriotic self-defense act", under which the state government pays for every firearm a private person buys at the market. Juss can therefore obtain as many firearms as he wants.

Because of various global crises, however, gasoline is very expensive, and Juss can obtain only $K$ units of it for the trip home. The states are connected by $M$ two-way highways, and one unit of gasoline covers a distance of $1$ km. Two states may be connected by more than one highway.

Moreover, not every state is enthusiastic about seeing millions of firearms on its streets. Different states therefore impose different limits on how many firearms one person may carry. In state $i$ a private person may carry at most $C_i$ firearms.

Taking into account both the limited amount of gasoline and the carry limits of the states he passes through, determine the maximum number of firearms Juss can bring home.

The first line contains three integers $N$, $M$, and $K$ ($2 \le N \le 10^5$, $1 \le M \le 10^5$, $1 \le K \le 10^9$): the number of states, the number of highways, and the amount of gasoline bought for the trip home.

The second line contains $N$ space-separated integers $c_i$ ($-1 \le c_i \le 10^9$), where $c_i$ is the carry limit in state $i$; if $c_i = -1$, that state has no limit. You may assume that states $1$ and $N$ have no limit.

Each of the following $M$ lines contains three integers $A_i$, $B_i$, and $L_i$ ($1 \le L_i \le 10^9$), meaning that states $A_i$ and $B_i$ are connected by a highway of length $L_i$ km. It is guaranteed that Juss can reach home using $K$ units of gasoline.

Print a single integer: the maximum number of firearms Juss can bring home. If he can carry an unlimited number, print $-1$ instead.