#include <bits/stdc++.h>
using namespace std;

const int N = 505, M = 1E7 + 5;

#define int long long
int head[N], n, m, cnt, gap[N], dep[N], dis[N], crr[N], cnt2 = 1, head2[N], s, t;
int inf = dis[N - 1];
bool vis[N];
struct edge {
    int u, v, w, next;
}E[M], EF[M];
void add(int u, int v, int w) {
    E[++cnt] = {u, v, w, head[u]};
    head[u] = cnt;
}

void add_edge(int u, int v, int w) {
   EF[++cnt2] = {u, v, w, head2[u]};
   head2[u] = cnt2;
}
#define E EF
bool bfs() {
    queue<int> q;
    memset(dep, 0, sizeof dep);
    dep[s] = 1;
    q.push(s);
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = E[i].next) {
            int v = E[i].v;
            if (E[i].w && dep[v] == 0) {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    } 
    if (dep[t] == 0) {
        return 0;
    }
    return 1;
}

int dfs(int u, int dis) {
    if (u == t) return dis;
    for (int i = head[u]; i; i = E[i].next) {
        int v = E[i].v;
        if (dep[v] == dep[u] + 1 && E[i].w) {
            int mi = dfs(v, min(dis, E[i].w));
            if (mi) {
                E[i].w -= mi;
                E[i ^ 1].w += mi;
                return mi;
            }
        }
    }
    return 0;
}

int dinic() {
    int ans = 0;
    while (bfs()) {
        int d;
        while (d = dfs(s, inf)) {
            ans += d;
        }
    }
    return ans;
}
#undef E
void spfa() {
    queue<int> q;
    memset(dis, 127, sizeof dis);
    q.push(1);
    vis[1] = 1;
    dis[1] = 0;
    while (q.size()) {
        int u = q.front(); vis[u] = 0;
        q.pop();
        for (int i = head[u]; i; i  = E[i].next) {
            int v = E[i].v, w = E[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

signed main() {
    cin >> n >> m;
    int t = n * 2 + 1;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w); 
        add(v, u, w);
    }
    spfa();
    for (int i = 1; i <= n; i++) {
        cin >> crr[i];
    }
    add_edge(s, 1, inf);
    add_edge(1, s, 0);
    add_edge(2 * n, t, inf);
    add_edge(t, 2 * n, 0);
    for (int i = 1; i <= n; i++) {
        if (i != 1 && i != n) {
            add_edge(i, i + n, crr[i]);
            add_edge(i + n, i, 0);
        } else {
            add_edge(i, i + n, inf);
            add_edge(i + n, i, 0);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = head[i]; j; j = E[j].next) {
            int v = E[j].v, w = E[j].w;
            if (dis[v] == dis[i] + w) {
                add_edge(i + n, v, inf);
                add_edge(v, i + n, 0);
            }
        }
    }
    cout << dinic();
}