#include <bits/stdc++.h>

using namespace std;

const int N = 50 + 10;
const int inf = 1000000000;

int g[N][N];
int s[N];

int main() {
	int n, m, u, v, w;
	cin >> n;
	for (int i=1; i<=n; i++) cin >> s[i];
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=n; j++) {
			if (i == j) g[i][j] = 0; else g[i][j] = inf;
		}
	}
	cin >> m;
	for (int i=0; i<m; i++) {
		cin >> u >> v >> w;
		g[u][v] = g[v][u] = min(g[u][v], w);
	}
	for (int k=1; k<=n; k++) {
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=n; j++) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
		}
	}
	int res = inf;
	for (int i=2; i<n-1; i++) {
		for (int j=i+1; j<n; j++) {
			res = min(res, g[1][i] + s[i] + g[i][j] + s[j] + g[j][n]);
			res = min(res, g[1][j] + s[j] + g[j][i]+ s[i] + g[i][n]);
		}
	}
	cout << res << endl;
	return 0;
}