Problem Description

Warrior Xiao Lan is preparing to explore the distant LQ maze and obtain the treasure inside. The maze can be seen as an undirected graph with $N$ vertices (numbered $0\sim N-1$) and $M$ edges. Each vertex has a monster, each monster has a certain attack power, and each edge has a weight $w$ representing the time Xiao Lan spends to traverse that edge.

To obtain the maze treasure, Xiao Lan needs to start from vertex $0$ and explore the map. When passing through a vertex, he may kill the monster there. Xiao Lan has a finishing move that guarantees defeating a monster in one hit. However, when Xiao Lan kills a monster, the monsters that are still alive on the vertices adjacent to the monster’s vertex will each attack Xiao Lan once (note: this does not include the monster being killed). Xiao Lan’s HP will be reduced by the corresponding attack power. Only after Xiao Lan has killed all monsters and reached vertex $N-1$, with HP greater than $0$ at that time, can he obtain the maze treasure.

Note that Xiao Lan’s finishing move is very fast, so killing a monster can be considered to take no time. A monster disappears after being killed once. Only when Xiao Lan kills a monster will the monsters on adjacent vertices attack Xiao Lan once.

If Xiao Lan can obtain the maze treasure, output the minimum time required. Otherwise, output $-1$.

Input Format

The first line contains three integers $N, M, HP$, separated by a single space, representing the number of vertices, the number of undirected edges, and Xiao Lan’s initial HP.

The second line contains $N$ integers, separated by a single space. The $i(0\le i\le N-1)$-th integer represents the attack power of the monster on the vertex with id $i$.

The next $M$ lines each contain three integers $u, v, w$, indicating that there is an undirected edge of weight $w$ between vertices $u$ and $v$.

Output Format

Output one line containing one integer as the answer. If Xiao Lan cannot obtain the maze treasure no matter what, output $-1$.

3 2 10
2 10 5
0 1 1
1 2 2

5

Hint

[Sample Explanation 1]

Xiao Lan starts at vertex $0$. The next step is to move to vertex $1$, costing time $1$.

Killing the monster at vertex $1$ will cause attacks from the monsters at vertices $0$ and $2$, reducing HP by $7$, leaving $3$ HP.

Move to vertex $0$, costing time $1$, then kill the monster at vertex $0$, and no attack is received.

Move to vertex $1$, then continue to vertex $2$, costing time $3$. Now kill the monster at vertex $2$, and no attack is received. After all kills, Xiao Lan has $3$ HP left, meeting the requirement. The total time cost is $5$.

[Constraints and Assumptions for Test Cases]

For $40\%$ of the test cases, $1\le N\le 10$.
For all test cases, $1\le N\le 15$, $1\le M\le N^2$, $1\le HP\le 100$, $1\le \text{monster attack power} \le 10$, $1\le w\le 10$.

Translated by ChatGPT 5