ISAP + SPFA

#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;
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) {
   E[++cnt2] = {u, v, w, head2[u]};
   head2[u] = cnt2;
}

void bfs() {
    queue<int> q;
    memset(dep, -1, sizeof dep);
    memset(gap, 0, sizeof gap);
    q.push(1);
    dep[t] = 0;
    gap[0] = 1;
    q.push(t);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head2[u]; i; i = EF[i].next) {
            int v = EF[i].v;
            if (dep[v] != -1) continue;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
            q.push(v);
        }
    }
}

long long ans = 0;
int dfs(int u, int flow) {
    if (u == t) {
        ans += flow;
        return flow;
    }
    int used = 0;
    for (int i = head2[u]; i; i = EF[i].next) {
        int v = EF[i].v;
        if (EF[i].w && dep[v] + 1 == dep[u]) {
            int mi = dfs(v, min(EF[i].w, flow - used));
            if (mi) {
                EF[i].w -= mi;
                EF[i ^ 1].w += mi;
                used += mi;
            }
            if (used == flow) return flow;
        }
    }
    if (--gap[dep[u]]) dep[s] = n + 1;
    dep[u]++;
    gap[dep[u]]++;
    return used;
}


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);
                }
            }
        }
    }
}

int ISAP() {
    ans = 0;
    bfs();
    while (dep[s] < n) dfs(s, dis[N]);
    return ans;
}

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, dis[N]);
    add_edge(1, s, 0);
    add_edge(2 * n, t, dis[N]);
    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, dis[N]);
            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, dis[N]);
                add_edge(v, i + n, 0);
            }
        }
    }
    cout << ISAP();
}