#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    const int inf=1<<23;
    int n, m;
    while (cin>>n) {
        vector<int> s(n);
        for(int& v: s) cin>>v;
        cin>>m;
        vector<vector<int>> cost(n, vector<int>(n, inf));
        while (m--) {
            int a, b, c;
            cin>>a>>b>>c;
            cost[a][b]=cost[b][a]=c;
        }
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
        rep(i, n) cost[i][i]=0;
        rep(k, n) rep(i, n) rep(j, n)
            cost[i][j]=min(cost[i][j], cost[i][k]+cost[k][j]);

        int res=inf;
        REP(i,1,n-1) REP(j,1,n-1) if (i!=j)
            res=min(res, cost[0][i]+s[i]+cost[i][j]+s[j]+cost[j][n-1]);
        cout<<res<<endl;
    }
}