#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int head[maxn],ver[maxn],nxt[maxn],cnt,dis[maxn];
int Head[maxn],Ver[maxn],Nxt[maxn],Cnt,Dis[maxn];
int dist[maxn],Dist[maxn],qwq[maxn],qaq[maxn];
void Add(int u,int v,int t) {
    Ver[++ Cnt] = v;
    Dis[Cnt] = t;
    Nxt[Cnt] = Head[u];
    Head[u] = Cnt;
    return ;
}
int n,m,price[maxn];
void add(int u,int v,int t) {
    ver[++ cnt] = v;
    dis[cnt] = t;
    nxt[cnt] = head[u];
    head[u] = cnt;
    return ;
}
queue<int> q;
bool vis[maxn];
void SPFA_dis(int* head,int* ver,int* nxt,int* dist,int s) {
    while(!q.empty())q.pop();
    memset(vis , false , sizeof(vis));
    memset(dist , 0x3f , sizeof(dist));
    dist[s] = 0;
    q.push(s);
    vis[s] = true;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u];i;i = nxt[i]) {
            int v = ver[i],w = dis[i];
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if(!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return ;
}
void SPFA(int* head,int* ver,int* nxt,int* dist,int s,bool p) {
    while(!q.empty())q.pop();
    memset(vis , false , sizeof(vis));
    if(p)memset(qaq , 0x3f , sizeof(qaq));//卖出 
    else memset(qwq , 0x3f , sizeof(qwq));//买入 
    qaq[s] = -price[s];
    qwq[s] = price[s];
    q.push(s);
    vis[s] = true;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u];i;i = nxt[i]) {
            int v = ver[i];
            if(p) {
                int t = min(qaq[u] + dis[i] , dist[u] + dis[i] - price[v]);
                if(qaq[v] > t) {
                    qaq[v] = t;
                    if(!vis[v]) {
                        q.push(v);
                        vis[v] = true;
//                        if(v == n) {
//                            printf("from:%d to:%d\n",u,v);
//                        }
                    }
                }
            }
            else {
                int t = min(qwq[u] + dis[i] , dist[u] + dis[i] + price[v]);
                if(qwq[v] > t) {
                    qwq[v] = t;
                    if(!vis[v]) {
                        q.push(v);
                        vis[v] = true;
                    }
                }
            }
        }
    }
    return ;
}
int main() {
    freopen("keepsake.in","r",stdin);
    freopen("keepsake.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;++ i) {
        int u,v,t;
        scanf("%d%d%d",&u,&v,&t);
        add(u , v , t);
        Add(v , u , t); 
    }
    for(int i = 1;i <= n;++ i)scanf("%d",&price[i]);
    SPFA_dis(head , ver , nxt , dist , 1);
    SPFA_dis(Head , Ver , Nxt , Dist , n);
    SPFA(head , ver , nxt , dist , 1 , false);
    SPFA(Head , Ver , Nxt , Dist ,n , true);
    int ans = 0x3f3f3f3f;
    for(int i = 1;i <= n;++ i) {
//        printf("%d %d\n",qwq[i],qaq[i]);
        ans = min(ans , qaq[i] + qwq[i]);
    }
    printf("%d\n",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}