P1462 The Road to Orgrimmar

On the continent of Azeroth, there is a remarkable warlock named Waizui O, a core member of the Horde. One day he wakes up and finds himself in the Alliance capital, Stormwind City. After being attacked by many Alliance soldiers, he decides to flee back to his home, Orgrimmar.

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.

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 a single integer: the minimal possible value of the maximum single-city toll along the route. If he cannot reach Orgrimmar, output `AFK`.

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