The Firearms Market

Time limit1sMemory limit1024 MB

Summary

Find the largest number of firearms that can be carried from state 1 to state N along a path of total length at most K, where each state on the path caps the carried amount and state 1 and N are uncapped.

Level: Medium7 of 10
Topics: Graph, Shortest path, Binary search, Greedy
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1

Input

6 7 54
-1 15 99 20 25 -1
1 2 10
2 6 15
1 3 50
3 6 20
1 4 14
4 5 18
5 6 22

Expected output

Example 2
Input
```
2 1 100
-1 -1
1 2 50
```
Expected output
```
-1
```