RT

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<set>


using namespace std;

#define int long long
#define ll long long
#define Endl cout<<endl;
#define ENdl Endl
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define lowbit(x) x&(-x)
#define fi first
#define se second
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int N=2e5+10;//注意修改
const int mod=1e9+7;
const int Max=0x3f3f3f3f3f;

int n,m;
int c[N];
struct id{
    int p,d;
};
int dis[N],vis[N];
vector<pii> ve[N];


void Dij(int s){
    for(int i=0;i<=n;i++) dis[i]=Max;
    dis[s]=0;
    priority_queue<pii,vector<pii> , greater<pii> >  q;
    q.push(make_pair(s,0));
    while(!q.empty()){
        int u=q.top().fi;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=0;i<ve[u].size();i++){
            pii y=ve[u][i];
            int v=y.fi,w=y.se;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(make_pair(v,dis[v]));
            }
        }
    }

}

/*
 */
signed main(){
    
//   freopen("a.in","r",stdin);
//   freopen("a.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        ve[u].push_back(make_pair(v,w+c[v]));
        ve[v].push_back(make_pair(u,w+c[u]));
    }
    Dij(1);
    cout<<dis[n]-c[n];
    return 0;
}



/*
 1
 5 3
 2 4 5

 */