#include <bits/stdc++.h>
using namespace std;

#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i =(j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
typedef long long ll;
const ll INFF = (ll)1e18;
const int INF = (int)1e9;
#define pb push_back

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<array<ll, 2>>> g(n + 1);
    vector<ll> v(n + 1);
    FOR(i, 1, n + 1, 1){
        cin >> v[i]; 
    }
    REP(i, m){
        int f, s, w;
        cin >> f >> s >> w;
        f++; s++;
        g[f].pb({s, w});
        g[s].pb({f, w});
    }
    priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
    vector<vector<array<ll, 2>>> dist(n + 1);
    auto print_dist = [&](){
        FOR(i, 1, n + 1, 1){
            REP(j, dist[i].size()){
                cout << "[" << dist[i][j][0] << " " << dist[i][j][1] << "]";
            }
            cout << endl;
        }
        cout << "...";
    };
    // array<ll, 2> -> {distance, from where}
    auto upd_dist = [&](int which, array<ll, 2> val){
        REP(j, dist[which].size()){
            if(dist[which][j][1] == val[1]){
                if(dist[which][j][0] > val[0]){
                    dist[which][j][0] = val[0];
                    return true;
                }
                return false;
            }
        }
        dist[which].pb(val); 
        sort(dist[which].begin(), dist[which].end());
        if(dist[which].size() <= 2){
            return true;
        }
        bool ret = true;
        if(dist[which].back()[1] == val[1]){
            ret = false;
        }
        dist[which].pop_back();
        return ret; 
    };
    FOR(i, 1, n + 1, 1){
        upd_dist(i, {v[i], i});
        pq.push({v[i], i, i});
    }
    //print_dist();
    while(!pq.empty()){
        while(!pq.empty()){
            auto tup = pq.top();
            int to = tup[1]; int from = tup[2];
            bool toproc = false;
            REP(j, dist[to].size()){
                if(dist[to][j][1] == from && dist[to][j][0] == tup[0]){
                    toproc = true;
                }
            }
            if(!toproc){
                pq.pop();
            }
            else{
                break;
            }
        }
        if(pq.empty()) break;
        auto tup = pq.top(); pq.pop();
        ll distance = tup[0]; 
        ll to = tup[1];
        ll from = tup[2];
        for(auto x : g[to]){
            bool ch = upd_dist(x[0], {distance + x[1], from});
            if(ch){
                pq.push({distance + x[1], x[0], from});
            }
        }
    }
    ll ans = INFF;
    FOR(i, 1, n + 1, 1){
        if(dist[i].size() == 2){
            ans = min(ans, dist[i][0][0] + dist[i][1][0]);
        }
    } 
    cout << ans << "\n";
    return 0;
}