Azeroth's Safe Passage

In Azeroth, there are \(n\) cities numbered \(1,2,3,\ldots,n\). There are \(m\) bidirectional highways connecting these cities. When traveling from one city to another, you will suffer a blood loss due to an Alliance attack; each road has an associated damage value. Furthermore, every time you visit a city (including the starting city and the destination), you have to pay a toll fee specific to that city. There are no toll booths on the roads.

Assume that city \(1\) is Stormwind and city \(n\) is Orgrimmar. You start your journey with a full health of \(b\). As soon as your health drops below zero at any point, you cannot proceed further.

Your goal is not to spend too much money. Among all paths from city \(1\) to city \(n\) that you can traverse without your health dropping below zero, you are to minimize the maximum toll fee that is paid at any city along your route. In other words, for a given path, let \(T\) be the maximum toll fee among the cities visited; you need to find the minimum possible \(T\) among all valid paths. If no such path exists, output \(-1\).

Note: A city is considered visited when it is either the starting point, an intermediate node, or the destination.

inputFormat

The input consists of multiple lines:

1. The first line contains three integers: \(n\), \(m\), and \(b\) — the number of cities, the number of roads, and the maximum health you have, respectively.
2. The second line contains \(n\) integers: \(c_1, c_2, \ldots, c_n\) where \(c_i\) is the toll fee for city \(i\).
3. The following \(m\) lines each contain three integers: \(u\), \(v\), and \(d\) representing a bidirectional road between city \(u\) and city \(v\) that causes a blood loss of \(d\) when traveling through it.

outputFormat

If there exists at least one path from city \(1\) to city \(n\) that can be traversed under the health constraint (i.e. the total damage along the path is at most \(b\)), output the minimum possible maximum toll fee encountered along such a path. Otherwise, output \(-1\).

sample

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

5