Reservoir Water Distribution

You are given a network of (N) reservoirs. Each reservoir (i) ((1 \leq i \leq N)) has a maximum water capacity (a_i). Additionally, there are (M) pipelines connecting pairs of reservoirs. Each pipeline is represented by three integers (u), (v), and (c), indicating that the pipeline connects reservoir (u) and reservoir (v) and can carry at most (c) units of water.

A water transfer from reservoir 1 to reservoir (N) must follow a single path. The water amount passing through each segment of the path is limited by the minimum among the current water amount, the capacity of the pipeline, and the capacity of the receiving reservoir. Formally, for a path

[ 1 \rightarrow i_2 \rightarrow \cdots \rightarrow N, ]

the maximum water flow is determined by:

[ \max_{\text{path}} ; \min{a_1, c_1, a_{i_2}, c_2, \dots, a_N} ]

Your task is to determine the maximum amount of water that can be transferred from reservoir 1 to reservoir (N) following these constraints.

inputFormat

The input is given via standard input (stdin) in the following format:

1. The first line contains an integer (N) representing the number of reservoirs.
2. The second line contains (N) space-separated integers representing the capacities (a_1, a_2, \dots, a_N) of the reservoirs.
3. The third line contains an integer (M) representing the number of pipelines.
4. Each of the next (M) lines contains three space-separated integers (u), (v), and (c), indicating a pipeline between reservoirs (u) and (v) with capacity (c).

outputFormat

Output a single integer to standard output (stdout) that represents the maximum amount of water that can be transferred from reservoir 1 to reservoir (N) according to the given constraints.## sample

5
10 20 30 40 50
4
1 2 15
2 3 10
3 4 25
4 5 20

10