import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
S=[int(input()) for _ in range(n)]
m=int(input())
from scipy.sparse.csgraph import floyd_warshall
table=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    table[a][b]=c
    table[b][a]=c
D=floyd_warshall(csgraph=table, directed=False, return_predecessors=False)
ans=float("inf")
import itertools
for i,j in itertools.combinations(range(1,n-1),2):
  ans=min(ans,S[i]+S[j]+D[i][j]+min(D[0][i]+D[j][n-1],D[0][j]+D[i][n-1]))
print(int(ans))