MAX = 1000000
N = input()
S = [input() for i in xrange(N)]
M = input()
d = [[MAX]*N for i in xrange(N)]
for i in xrange(N):
	d[i][i] = 0
for i in xrange(M):
	a,b,c = map(int,raw_input().split())
	d[a][b] = d[b][a] = c
for k in xrange(N):
	for i in xrange(N):
		for j in xrange(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 xrange(1,N-1) for j in xrange(1,N-1) if i != j)