#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAX = 1e3+5;
const int MOD = 1e9+7;
const ll INF = INT_MAX;
const ll _INF = INT_MIN;

int n, m;
int val[MAX];
vector<pii> adj[MAX];
int dis[MAX], ans[MAX];
bool processed[MAX];
priority_queue<tuple<int, int, int> > vq;

int solve() {
    fill(dis+1, dis+1+n, INF);
    fill(processed+1, processed+1+n, false);

    dis[1] = 0;
    ans[1] = val[1];
    vq.push(make_tuple(0, val[1], 1));
    while(!vq.empty()) {
        int v = get<2>(vq.top());
        vq.pop();

        if(processed[v]) continue;
        if(v == n) return ans[v];
        processed[v] = true;

        int s = sz(adj[v]);
        fo(i, 0, s-1) {
            int id = adj[v][i].fi, w = adj[v][i].se;
            if(dis[v]+w < dis[id] || (dis[v]+w == dis[id] && ans[v]+val[id] > ans[id])) {
                dis[id] = dis[v]+w;
                ans[id] = ans[v]+val[id];
                vq.push(make_tuple(-dis[id], ans[id], id));
            }
        }
    }

    return 0;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    fo(i, 1, n) cin >> val[i];
    cin >> m;
    while(m--) {
        int p, q, u;
        cin >> p >> q >> u;
        adj[p].pb(mk(q, u));
        adj[q].pb(mk(p, u));
    }

    cout << solve();
}