rt，只有40pts，其他全部MLE，不知道为什么

code：

#include <bits/stdc++.h>

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

const int N = 2005, M = 1e5 + 5;
const ll I = 1e18;

struct V {
  ll d;
  int fe, ne;
} v[N];

struct E {
  int y, n;
  ll c;
} e[M << 1];

vector<pii> _e[N];
int n, m, s, t, idx = 1;
ll d[N], c[N], ans;
bool b[N];

void Add(int x, int y, ll z) {
  e[++idx] = {y, v[x].fe, z};
  v[x].fe = idx;
  e[++idx] = {x, v[y].fe, 0};
  v[y].fe = idx;
}

bool Bfs() {
  for (int i = 1; i <= t; ++i) {
    v[i].d = i == s, v[i].ne = v[i].fe;
  }
  queue<int> q;
  for (q.push(s); !q.empty(); q.pop()) {
    int x = q.front();
    for (int i = v[x].fe; i; i = e[i].n) {
      if (!v[e[i].y].d && e[i].c) {
        v[e[i].y].d = v[x].d + 1;
        q.push(e[i].y);
      }
    }
  }
  return v[t].d;
}

ll Dfs(int x, ll b) {
  if (x == t) {
    return b;
  }
  ll _b = b;
  for (int &i = v[x].ne; i && b; b && (i = e[i].n)) {
    ll a = Dfs(e[i].y, min(e[i].c, b));
    b -= a, e[i].c -= a, e[i ^ 1].c += a;
  }
  return _b - b;
}

void SPFA() {
  for (int i = 2; i <= n; ++i) {
    d[i] = I;
  }
  queue<int> q;
  for (q.push(s), b[s] = 1; !q.empty(); q.pop()) {
    int x = q.front();
    b[x] = 0;
    for (pii i : _e[x]) {
      if (d[i.first] > d[x] + i.second) {
        d[i.first] = d[x] + i.second;
        if (!b[i.first]) {
          q.push(i.first), b[i.first] = 1;
        }
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1, x, y, z; i <= m; ++i) {
    cin >> x >> y >> z;
    _e[x].emplace_back(y, z);
    _e[y].emplace_back(x, z);
  }
  s = 1, t = n << 1;
  SPFA();
  for (int i = 1; i <= n; ++i) {
    cin >> c[i];
  }
  for (int i = 1; i <= n; ++i) {
    if (i != 1 && i != n) {
      Add(i, i + n, c[i]);
    } else {
      Add(i, i + n, I);
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (pii j : _e[i]) {
      if (d[j.first] == d[i] + j.second) {
        Add(i + n, j.first, I);
      }
    }
  }
  for (; Bfs(); ans += Dfs(s, I)) {
  }
  cout << ans;
  return 0;
}