#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

#define POS(i,j) ((i)*n+(j))

void run(void){
  int n;
  scanf("%d",&n);
  int s[50];
  int i,j,k;
  for(i=0;i<n;i++) scanf("%d",s+i);
  int m;
  scanf("%d",&m);
  const int inf=100000;
  int c[2500];
  for(i=0;i<n;i++) for(j=0;j<n;j++) c[POS(i,j)]=(i==j)?0:inf;
  for(i=0;i<m;i++){
    int a,b,cc;
    scanf("%d%d%d",&a,&b,&cc);
    c[POS(a,b)]=cc;
    c[POS(b,a)]=cc;
  }
  for(k=0;k<n;k++){
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
	c[POS(i,j)]=MIN(c[POS(i,j)],c[POS(i,k)]+c[POS(k,j)]);
      }
    }
  }
  int min=inf;
  for(i=1;i<n-1;i++){
    for(j=1;j<n-1;j++){
      if(i==j) continue;
      min=MIN(min,c[POS(0,i)]+s[i]+c[POS(i,j)]+s[j]+c[POS(j,n-1)]);
    }
  }
  printf("%d\n",min);
}

int main(void){
  run();
  return 0;
}