問題文

$0$から$N-1$までの$N$個の地点がある。
地点から地点の移動コストが$M$個与えられる。
また各地点に滞在コストがある。

$0$地点から$N-1$地点にたどり着くまでに、 $0$地点と$N-1$地点以外の異なる$2$つの地点に滞在しなければならない。
滞在する地点は自由に決めて良い。
この条件での移動コストと滞在コストの合計の最小値を求めよ。

都市を通るけど、滞在しないこともできます。

入力

$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$

一行目は地点の数$N(4\le N\le 50)$が与えられる。
その後の$N$行は$0$地点から$N-1$地点までの$N$個の地点の滞在コスト$S_i(1\le S_i\le 1000,0\le i\le N-1)$ が与えられる。
ただし、$0$地点と$N-1$地点の滞在コストは$0$で与えられる。

その次の行は、移動についての情報が$M$個 $(1\le M\le N(N-1)/2)$ が与えられる。
その後の$M$行は移動元$A_j(0\le A_j\le N-1)$、移動先$B_j(0\le B_j\le N-1)$、移動コスト$C_j(1\le C_j\le 1000)$の順で$M$個の情報が与えられる。$(1\le j\le M)$

「$A_j$から$B_j$」また「$B_j$から$A_j$」のどちらも移動可能とする。（つまり無向グラフ）
$A_j\ne B_j$は保証されている。
$A_j$から$B_j$（その逆も含む）への遷移は複数ないとする。

$0$地点から$N-1$地点には必ずたどり着ける経路があることが保証される。
さらに$0$地点と$N-1$地点以外の異なる$2$つの地点に滞在することができることが保証される。
2015/07/08 20:53追記
$0$地点から辿りつけない地点もあることに注意。

移動コストと滞在コストの単位は同一とし、加算できるものとする。

出力

移動コストと滞在コストの合計の最小値を一行で出力してください。
最後に改行してください。

サンプル

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