#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
#define printall(n,array) for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;
typedef long long ll;
typedef pair<int, int> PI;
typedef pair<int, PI> V;
typedef vector<int> VE;
const ll mod = 1000000007; //10^9+7

int d[52][52];
int n;
int m;
int s[52];
int a[1300];
int b[1300];
int c[1300];

void warshall_floyd(){
  REP(k,n){
    REP(i,n){
      REP(j,n){
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        d[j][i]=d[i][j];
      }
    }
  }
}

int main(){
  cin>>n;
  REP(i,n)cin>>s[i];
  cin>>m;
  REP(i,n)REP(j,n)d[i][j]=mod;
  REP(i,n)d[i][i]=0;
  REP(i,m){
    cin>>a[i]>>b[i]>>c[i];
    d[a[i]][b[i]]=c[i];
  }
  warshall_floyd();
  //REP(i,n)REP(j,n)print(i<<" "<<j<<" "<<d[i][j]);///
  //print(d[0][n-1]);///
  int ans=mod;
  rep(i,1,n-1)rep(j,i+1,n-1){
    int ss=s[i]+s[j];
    int min_=min(d[0][i]+d[i][j]+d[j][n-1],d[0][j]+d[i][j]+d[i][n-1]);
    ///print(i<<" "<<j<<" "<<min_<<" "<<ss);
    ans=min(ans,min_+ss);
  }
  print(ans);
}