Warrior Xiaolan and the LQ Maze Treasure

Warrior Xiaolan is preparing to explore the distant LQ maze in order to obtain the treasure hidden inside. The maze is represented as an undirected graph with $N$ vertices (numbered from $0$ to $N-1$) and $M$ edges. Each vertex contains a monster with an attack power $a_i$, and every edge has a weight $w$ indicating the time it takes for Xiaolan to traverse that edge.

Starting from vertex $0$, Xiaolan must travel through the maze and kill the monster at every vertex. He can eliminate a monster instantly using his special ultimate attack (which consumes no time). However, whenever he kills a monster at vertex $v$, every monster that is still alive in a vertex adjacent to $v$ will launch a counterattack, reducing his health by their respective attack powers. (Note that the monster at vertex $v$, which is being killed, does not counterattack.)

After all monsters have been defeated and Xiaolan reaches vertex $N-1$ with his remaining health greater than $0$, he will obtain the maze treasure.

Crucial observation: When Xiaolan kills a monster at vertex $v$, the damage he receives is the sum of the attack powers of all adjacent vertices that still have their monsters alive. In an optimal killing order, every edge \( (u,v) \) contributes exactly \( \min(a_u, a_v) \) damage, so the total damage taken is \( \sum_{(u,v) \in E} \min(a_u, a_v) \). You are given Xiaolan's initial health $H$. If the total damage is at least $H$, even an optimal strategy cannot keep his health above zero.

Your task is to determine the minimum time Xiaolan must spend traversing the maze (note that killing monsters costs no time) so that he can kill all monsters and reach vertex $N-1$ with his health still positive. If it is impossible for him to obtain the treasure, output \(-1\).

inputFormat

The first line contains three integers \(N\), \(M\), and \(H\) — the number of vertices, the number of edges, and Xiaolan's initial health.

The second line contains \(N\) integers where the \(i\)-th integer represents the attack power of the monster at vertex \(i\) (\(0 \le i \le N-1\)).

The following \(M\) lines each contain three integers \(u\), \(v\), and \(w\), indicating there is an undirected edge between vertices \(u\) and \(v\) with weight \(w\).

outputFormat

If it is possible for Xiaolan to obtain the treasure, output the minimum time required. Otherwise, output \(-1\).

sample

3 3 10
3 5 2
0 1 4
1 2 6
0 2 8

10