Problem Statement

There are \(N\) locations numbered from \(0\) to \(N-1\).
\(M\) movement costs between locations are given.
Each location also has a stay cost.

On the way from location \(0\) to location \(N-1\), you must stay at \(2\) distinct locations other than location \(0\) and location \(N-1\).
You may freely choose the locations to stay at.
Find the minimum total of movement costs and stay costs under this condition.

You may also pass through a city without staying there.

Input

\(N\)
\(S_0\)
\(S_1\)
\(\dots\)
\(S_i\)
\(\dots\)
\(S_{N-1}\)
\(M\)
\(A_1\ B_1\ C_1\)
\(A_2\ B_2\ C_2\)
\(\dots\)
\(A_j\ B_j\ C_j\)
\(\dots\)
\(A_M\ B_M\ C_M\)

The first line gives the number of locations \(N\ (4 \leq N \leq 50)\).
The following \(N\) lines give the stay costs \(S_i\ (1 \leq S_i \leq 1000, 0 \leq i \leq N-1)\) of the \(N\) locations from location \(0\) to location \(N-1\).
However, the stay costs of location \(0\) and location \(N-1\) are given as \(0\).

The next line gives the number \(M\) \((1 \leq M \leq N(N-1)/2)\) of pieces of movement information.
The following \(M\) lines give \(M\) pieces of information, each in the order: source \(A_j\ (0 \leq A_j \leq N-1)\), destination \(B_j\ (0 \leq B_j \leq N-1)\), movement cost \(C_j\ (1 \leq C_j \leq 1000)\). \((1 \leq j \leq M)\)

Movement is possible both "from \(A_j\) to \(B_j\)" and "from \(B_j\) to \(A_j\)". (That is, the graph is undirected.)
It is guaranteed that \(A_j \neq B_j\).
There are no multiple transitions from \(A_j\) to \(B_j\) (including the reverse direction).

It is guaranteed that there is a route from location \(0\) to location \(N-1\).
It is further guaranteed that it is possible to stay at \(2\) distinct locations other than location \(0\) and location \(N-1\).
Added 2015/07/08 20:53
Note that there may be locations unreachable from location $0$.

Movement costs and stay costs are in the same unit and can be added together.

Output

Output the minimum total of movement costs and stay costs on one line.
Print a newline at the end.

Sample

4
0
2
100
0
5
0 1 1
0 2 1
1 2 1
1 3 1
2 3 2

105

4
0
3
3
0
3
0 1 1
1 3 2
2 3 4

17

16
0
15
6
23
8
193
14
13
53
16
85
12
15
5
14
0
15
0 1 17
14 15 18
7 8 87
4 5 137
8 9 17
11 12 33
5 6 177
9 10 47
10 11 27
1 2 77
6 7 114
12 13 15
2 3 127
13 14 11
3 4 85

1000