#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define ll long long

using namespace std;

const int L = 20000;

vector< pair<int, int> > graf[20000];
int w[L];
bool byl[L];
long long mi;

int main()
{
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> w[i];
    for(int i = 0; i < m; i++){
        int a, b, we;
        cin >> a >> b >> we;
        graf[a].push_back({b,we});
        graf[b].push_back({a,we});
    }
    mi = L*L;
    priority_queue< pair<long long, int> > fr;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) byl[j] = 0;
        fr.push({-w[i],i});
        while(!fr.empty()){
            pair< ll, int> tu = fr.top();
            fr.pop();
            int v = tu.second;
            if(byl[v]) continue;
            byl[v] = 1;
            if(v!= i) mi = min(mi, -tu.first+w[v]);
            //cout << i << " " << v << " " << mi << endl;
            for(int j = 0; j < graf[v].size(); j++){
                int kam = graf[v][j].first;
                int kolik = graf[v][j].second;
                if(!byl[kam] && kam > i && -tu.first + kolik < mi) fr.push({tu.first-kolik,kam});
            }
        }
    }
    cout << mi << endl;
    return 0;
}