#include <bits/stdc++.h>
using namespace std;
const int N=50000+5;
const int M=100000+5;
struct wer{
	int pt,d,s;
	bool operator<(const wer&x)const{
		return x.d+x.s<d+s;
	}
};
struct sdf{
    int to,next,w;
}eg1[M],eg2[M];
int head1[N]={0},head2[N]={0},ne=0;
int p[N];
int mn[N],mx[N];
int mnp[N],mxp[N];
int n,m;
void add(int x,int y,int z){
    eg1[++ne]={y,head1[x],z};
    head1[x]=ne;
    eg2[ne]={x,head2[y],z};
    head2[y]=ne;
    return ;
}
bool vis[N]={0};
void dij1(){
    memset(mn,0x3f,sizeof(mn));
    memset(mnp,0x3f,sizeof(mnp));
    priority_queue<wer>q;
    q.push({1,0,p[1]});
    mnp[1]=p[1];
    mn[1]=0;
    while(!q.empty()){
        int u=q.top().pt;q.pop();
        if (vis[u]==1)continue;
        vis[u]=1;
        for (int i=head1[u];i!=0;i=eg1[i].next){
            int v=eg1[i].to,w=eg1[i].w;
            if (mn[u]+w<mn[v]){
                mnp[v]=min(mnp[u],min(p[v],mnp[v]));
                mn[v]=min(mn[u]+w,mn[v]);
                q.push({v,mn[v],mnp[v]});
            }
        }
    }
}
void dij2(){
    memset(mx,0x3f,sizeof(mx));
    memset(mxp,0,sizeof(mxp));
    memset(vis,0,sizeof(vis));
    priority_queue<wer>q;
    q.push({n,0,p[n]});
    mxp[n]=p[n];
    mx[n]=0;
    while(!q.empty()){
        int u=q.top().pt;q.pop();
        if (vis[u]==1)continue;
        vis[u]=1;
        for (int i=head2[u];i!=0;i=eg2[i].next){
            int v=eg2[i].to,w=eg2[i].w;
            if (mx[u]+w<mx[v]){
                mxp[v]=max(mxp[u],max(p[v],mxp[v]));
                mx[v]=min(mx[u]+w,mx[v]);
                q.push({v,mx[v],mxp[v]});
            }
        }
    }
}
int main(){
    freopen ("keepsake.in","r",stdin);
    freopen ("keepsake.out","w",stdout);
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    for (int i=1;i<=n;i++){
        scanf("%d",&p[i]);
    }
    dij1();
    dij2();
    int ans=0x7fffffff;
    for (int i=1;i<=n;i++){
        ans=min(ans,mn[i]+mx[i]-mxp[i]+mnp[i]);
    }
    cout<<ans<<endl;
}