import sequtils,strutils,math
var
    N = stdin.readline.parseInt
    S = newSeq[int](0)
    A,B,C : int
    mcos : int
    ans = high(int)
    table : array[50,array[50,int]]
    
for n in 0..<N:
    S.add(stdin.readline.parseInt)
for i in 0..<N:
    for j in 0..<N:
        table[i][j] = 100000
var M = stdin.readline.parseInt
for m in 0..<M:
    (A,B,C) = stdin.readline.split.map(parseInt)
    table[A][B] = C
    table[B][A] = C
var flag = true
while flag:
    flag = false
    for i in 0..<N:
        for j in 0..<N:
            for k in 0..<N:
                if table[i][j] > table[i][k] + table[k][j]:
                    flag = true
                    table[i][j] = table[i][k] + table[k][j]
for i in 1..N - 2:
    for j in 1..N - 2:
        if i == j:
            continue
        mcos = min(@[table[0][i] + table[i][j] + table[j][N - 1],
            table[0][N - 1] + table[N - 1][i] * 2 + table[N - 1][j] * 2,
            table[0][i] + table[i][N - 1] + table[N - 1][j] * 2])
        ans = min(ans,mcos + S[i] + S[j])
echo ans