import static java.lang.Math.*;

import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] s=new int[n];
		for(int i=0;i<n;i++) {
			s[i]=sc.nextInt();
		}
		int m=sc.nextInt();
		int[][] graph=new int[n][n];
		for(int i=0;i<n;i++) {
			Arrays.fill(graph[i], Integer.MAX_VALUE>>4);
		}
		for(int i=0;i<m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			int c=sc.nextInt();
			graph[a][b]=c;
			graph[b][a]=c;
		}
		for(int i=0;i<n;i++) {
			//System.out.println(Arrays.toString(graph[i]));
		}
		int[][] d=new int[n][n];
		for(int i=0;i<n;i++) {
			d[i]=graph[i];
		}
		for(int k=0;k<n;k++) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
				}
			}
		}
		int min=Integer.MAX_VALUE;
		for(int i=1;i<n-1;i++) {
			for(int j=1;j<n-1;j++) {
				if(i==j)continue;
				min=min(min,d[0][i]+s[i]+d[i][j]+s[j]+d[j][n-1]);
			}
		}
		System.out.println(min);
	}

}