import java.util.*;

public class Main {
	
	static Scanner sc;
	static int n,m;
	static void Warshall_Floyd_Algorithm(int n, int N[][]) {
		for (int i = 0; i < n; i++) {
			Arrays.fill(N[i], Integer.MAX_VALUE / 2);
			N[i][i] = 0;
		}
		for(int i=0;i<m;i++){
			int x=sc.nextInt();
			int y=sc.nextInt();
			int c=sc.nextInt();
			N[x][y]=N[y][x]=c;
		}
		//初期条件をここに挿入
		for (int k = 0; k < n; ++k) {
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					N[i][j] = Math.min(N[i][j], N[i][k] + N[k][j]);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		sc=new Scanner(System.in);
		n=sc.nextInt();
		int s[]=new int[n];
		for(int i=0;i<n;i++){
			s[i]=sc.nextInt();
		}
		int map[][]=new int[n][n];
		
		m=sc.nextInt();
		Warshall_Floyd_Algorithm(n,map);
		int ans=Integer.MAX_VALUE;
		for(int i=1;i<n-1;i++){
			for(int j=1;j<n-1;j++){
				if(i==j)continue;
				ans=Math.min(ans,map[0][i]+s[i]+map[i][j]+s[j]+map[j][n-1]);
			}
		}
		System.out.println(ans);
		
	}}