the galactic trade federation needs to transport essential supplies across a network of star systems. there are N space stations, numbered 1 to N, connected by M bidirectional hyperlanes. each hyperlane connects two stations and takes a certain amount of fuel to traverse.

however, space pirates are active! each station i has a danger level Di. the federation wants to send a cargo ship from station 1 to station N. to minimize risk, the captain refuses to visit any station where the danger level is strictly greater than a threshold X.

your task is to find the minimum fuel cost to travel from station 1 to station N, such that the maximum danger level of any station visited on the path is at most X. if no such path exists for a given X, output -1.

because the Federation is testing multiple shipping routes under different pirate threat levels, you must answer Q independent queries, each with a different value of X.

input format

• the first line contains three integers: N (number of stations), M (number of hyperlanes), and Q (number of queries).
• the second line contains N integers: D1, D2, ... , DN, representing the danger level of each station.
• the next M lines each contain three integers: u, v, and w, representing a bidirectional hyperlane between station u and station v with a fuel cost of w.
• the next Q lines each contain a single integer: X, the maximum allowed danger level for that query.

output format

for each of the Q series, print a single integer on a new line: the minimum fuel cost required, or -1 if station N is unreachable under the danger constraint.

constraints

• 2 <= N <= 10^5
• 1 <= M <= 2 x 10^5
• 1 <= Q <= 10^5
• 1 <= Di, X <= 10^9
• 1 <= u,v <= N (u is not v)
• 1 <= w <= 10^9
• the graph may contain multiple edges between the same pair of stations, but no self-loops.