#include<bits/stdc++.h>
#define rep(i,j,k) for(int i = (j) ; i <= (k) ; i++)
#define fdow (i,j,k) for (int  i = (j) ; i >= (k) ; i--)
#define debug puts("Debeg!!!!! wake up !!!")
#define Mset(a,v) memset(a,v,sizeof (a))
#define Mcpy(a,v) memcpy(a,v,sizeof (a))
#define mrep(i,j) for(int i=(h[j]);~i;i=ne[i])

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N = 1000+9;
const int M = 4e5+9;
const ll INF= 1e18+9;
int h[N], e[M], ne[M], idx;
int cur[N];
ll w[M];
ll d[N],f[M];
bool st[N];
int n,m,S,T;

struct edge
{
    int from,to;
    ll val;
}Q[M];

template <typename T> void inline read(T &x)
{
    x= 0 ; bool f= 0; char ch  = getchar();
    while (ch < '0' || ch > '9') {if(ch == '-')f= 1; ch = getchar();}
    while (ch <='9' && ch >= '0') {x= (x<<1)+ (x<<3) + ch - '0'; ch = getchar();}
    if(f)x*=-1;
}

template <typename T> inline void wri(T x)
{
    if(x<0)putchar('-'), x= -x;
    if(x>9)wri(x/10);
    putchar(x%10 +'0');
}


void add_gra(int a,int b,ll c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, w[idx] = c, ne[idx] = h[b], h[b] = idx ++ ;
}

void add_flow(int a, int b, ll c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
    memset(d,-1,sizeof d);
    queue<int>q;
    q.push(S); d[S]=0; cur[S]=h[S];
    while (q.size())
    {
        int top = q.front();
        q.pop();
        for(int i=h[top];~i;i=ne[i])
        {
            int v= e[i];
            if(d[v]==-1 && f[i])
            {
                d[v]=d[top]+1;
                cur[v]=h[v];
                if(v==T)return 1;
                q.push(v);
            }
        }
    }
    return 0;
}

ll find(int u,ll lim)
{
    ll flow = 0;
    if(u==T)return lim;
    for (int i=cur[u];~i&&flow<lim;i=ne[i])
    {
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i])
        {
            ll tx=find(v,min(f[i],lim-flow));
            if(!tx)d[v]=-1;
            f[i^1]+=tx; f[i]-=tx; flow += tx;
        }
    }
    return flow;
}

void spfa()
{
    queue<int> q;
    rep(i,1,n) d[i]=INF;
    q.push(S); d[S]=0; st[S]=1;
    while(q.size())
    {
        int top = q.front();
        q.pop();
        st[top]=0;
        mrep(i,top)
        {
            int v=e[i];
            if( d[v] > d[top]+w[i])
            {
                d[v]=d[top]+w[i];
                if(!st[v]) q.push(v),st[v]=1;
            }
        }
    }
}


ll Dinic()
{
    ll res= 0;
    ll flow;
    while (bfs()) while (flow=find(S,LONG_LONG_MAX))res+=flow;
    return res;
}

int main()
{
    Mset(h,-1);
    read(n); read(m);

    S = 1;
    T = n;

    rep(i,1,m)
    {
        int u,v;
        ll dis;
        read(u); read(v); read(dis);
        add_gra(u,v,dis);
        Q[i]={u,v,dis};
    }
    spfa();

    Mset(h,-1);
    idx = 0;
    rep(i,1,m)
    {
        int u,v;
        ll dis;
        u=Q[i].from; v=Q[i].to; dis=Q[i].val;
        if(d[u]+dis==d[v])
        {
            add_flow(u+n,v,INF);
            add_flow(v+n,u,INF);
        }
    }

    rep(i,1,n)
    {
        ll x;
        read(x);
        if(i!=1 && i!=n)add_flow(i,i+n,x);
        else add_flow(i,i+n,INF);
    }

    S = 1;
    T = n+n;
    printf("%lld",Dinic());

}