Description

There are $n$ cities in Azeroth, numbered $1, 2, 3, \ldots, n$.

There are $m$ undirected roads between cities. Traveling from one city to another will trigger attacks by the Alliance, causing a certain amount of health loss.

Each time he passes through a city, he must pay a toll (including the start and the end). There are no toll booths along the roads.

Assume $1$ is Stormwind City, $n$ is Orgrimmar, and his maximum health is $b$. At the start, his health is full. If his health drops below zero, he cannot reach Orgrimmar.

Waizui O does not want to spend too much money. Among all routes that can reach Orgrimmar, consider the maximum single-city toll along the route; find the minimal possible value of this maximum.

Input Format

The first line contains 3 positive integers, $n, m, b$, representing the number of cities, the number of roads, and Waizui O’s health $b$.

Then follow $n$ lines, each containing 1 non-negative integer, $f_i$, meaning that passing city $i$ requires a toll of $f_i$.

Then follow $m$ lines, each containing 3 positive integers, $a_i, b_i, c_i$ ($1\leq a_i,b_i\leq n$). This means there is a two-way road between cities $a_i$ and $b_i$. If you travel from city $a_i$ to city $b_i$, or from city $b_i$ to city $a_i$, you will lose $c_i$ health.

Output Format

Output a single integer: the minimal possible value of the maximum single-city toll along the route.

If he cannot reach Orgrimmar, output AFK.

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

10

Hint

Constraints:

• For $60\%$ of the testdata, $n\leq 200$, $m\leq 10^4$, $b\leq 200$.
• For $100\%$ of the testdata, $1\leq n\leq 10^4$, $1\leq m\leq 5\times 10^4$, $1\leq b\leq 10^9$.
• For $100\%$ of the testdata, $1\leq c_i\leq 10^9$, $0\leq f_i\leq 10^9$. There may be two edges connecting the same pair of cities.

Translated by ChatGPT 5