R=range;I=input;N=I();S=[I()for i in R(N)];M=I()
d = [N*[10**6]for i in R(N)]
for i in R(N):d[i][i]=0
for i in R(M):a,b,c=map(int,raw_input().split());d[a][b]=d[b][a]=c
for k in R(N):
	for i in R(N):
		for j in R(N):d[i][j]=min(d[i][j],d[i][k]+d[k][j])
print min(d[0][i]+d[i][j]+d[j][N-1]+S[i]+S[j]for i in R(1,N-1)for j in R(1,N-1)if i!=j)