def read_data():
    N = int(input())
    S = [int(input()) for n in range(N)]
    M = int(input())
    dist = [[float('inf')] * N for n in range(N)]
    for n in range(N):
        dist[n][n] = 0
    for m in range(M):
        A, B, C = map(int, input().split())
        dist[A][B] = C
        dist[B][A] = C
    return N, S, dist

def solve(N, S, dist):
    for i in range(N):
        dist_i = dist[i]
        for j in range(N):
            for k in range(N):
                dist[i][j] = min(dist_i[j], dist_i[k] + dist[k][j])
    mincost = float('inf')
    for i in range(1, N-1):
        for j in range(1, N-1):
            if i == j:
                continue
            cost = dist[0][i] + dist[i][j] + dist[j][N-1] + S[i] + S[j]
            if cost < mincost:
                mincost = cost
    return mincost

N, S, dist = read_data()
print(solve(N, S, dist))