【题意】
给你一个有点权和边权的图，让你找出一个子图，使得其边权和-点权和最大。

【思路】
感觉是一道很难的题。

第一眼感觉要用网络流来做，因为这个问题有非常复杂的性质。

思考了很久以后发现可以假设先把所有边权选上，然后思考最多保留多少，也就是要么变成某个最小割，如果这条边想要保留就要花费选择点的费用，不然就要花费删掉这条边的费用。

又思考了很久，想到了“要么就要删掉一条边，要么就要选择两个点”这个性质，然后意识到可以以点代边，也就是二分图，左边是边，从源点连$C_i$的边，右边是点，往汇点连$V_i$的边，然后对于每条边往$A_i+m$和$B_i+m$连$inf$的边即可。

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

const int N = 6e4 + 10, M = 5e5 + 10;

int n, m;
int st, ed;
int tot = 1, hd[N], cur[N], ver[M], nxt[M], w[M];
int h[N];

void add(int x, int y, int z) {
    tot++;
    ver[tot] = y; w[tot] = z;
    nxt[tot] = hd[x];
    hd[x] = tot;
}
void link(int x, int y, int z) {
    add(x, y, z), add(y, x, 0 );
}
bool bt_h() {
    for (int i = 1; i <= ed; i++) h[i] = -1;
    h[st] = 1;
    queue<int> q; q.push(st);
    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = hd[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (w[i] && h[y] == -1) {
                h[y] = h[x] + 1;
                q.push(y);
            }
        }
    }
    return h[ed] != -1;
}
int findflow(int x, int f) {
    if (x == ed) return f;
    int res = f, tt;
    for (int &i = cur[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (w[i] && h[y] == h[x] + 1) {
            tt = findflow(y, min(w[i], res));
            w[i] -= tt, w[i ^ 1] += tt;
            res -= tt; if (!res) break;
        }
    }
    if (res == f) h[x] = 0;
    return f - res;
}
int dinic() {
    int ans = 0;
    while (bt_h()) {
        memcpy(cur, hd, sizeof(cur));
        ans += findflow(st, 1e9);
    }
    return ans;
}

int main() {
    // freopen("in.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    st = n + m + 1, ed = st + 1;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        link(m + i, ed, x);
    }
    int tot = 0;
    for (int i = 1; i <= m; i++) {
        int x, y, z; cin >> x >> y >> z;
        link(st, i, z);
        link(i, m + x, 1e9);
        link(i, m + y, 1e9);
        tot += z;
    }
    cout << tot - dinic() << endl;
}