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