#include <fstream>
#include <queue>
#include <list>
using namespace std;
 
#define min(a,b) ((a < b) ? a : b)
#define oo 0x3f3f3f3f
 
ifstream fin ("traseu.in");
ofstream fout ("traseu.out");
 
vector <list <int> > g;
vector <int> GI, GE, t, dist;
vector <vector <int> > C, F, cost;
vector <bool> q;
queue <int> Q;
int n, m, s, d, sol;
 
void Resizeall(int x) {
    GE.resize(x); GI.resize(x);
    F.resize(x); C.resize(x);
    t.resize(x); dist.resize(x);
    cost.resize(x); q.resize(x);
    g.resize(x);
    for (int i = 0; i < x; ++i)
        C[i].resize(x), F[i].resize(x), cost[i].resize(x);
}
 
bool bellmanford() {
    dist.assign(d+1, oo);
    q.assign(d+1, 0);
    t.assign(d+1, -1);
    Q.push(s);
    q[s] = 1;
    dist[s] = 0;
    t[s] = s;
    while (Q.size()) {
        int x = Q.front();
        Q.pop();
        q[x] = 0;
        for (list <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
            if (F[x][*it] < C[x][*it] && dist[x] + cost[x][*it] < dist[*it]) {
                dist[*it] = dist[x] + cost[x][*it];
                t[*it] = x;
                if (!q[*it]) {
                    Q.push(*it);
                    q[*it] = 1;
                }
            }
    }
    return (dist[d] != oo);
}
 
int main() {
    fin >> n >> m;
    Resizeall(n+2);
    while (m--) {
        int x, y, z;
        fin >> x >> y >> z;
        cost[x][y] = z;
        cost[y][x] = -z;
        sol += z;
        C[x][y] = oo;
        g[x].push_back(y);
        g[y].push_back(x);
        GE[x]++;
        GI[y]++;
    }
    d = n + 1;
    for (int i = 1; i <= n; ++i) {
        if (GI[i] < GE[i]) {
            g[i].push_back(d);
            C[i][d] = GE[i] - GI[i];
        }
        if (GE[i] < GI[i]) {
            g[s].push_back(i);
            C[s][i] = GI[i] - GE[i];
        }
    }
    fin.close();
    while (bellmanford()) {
        int flux = oo;
        for (int x = d; x; x = t[x])
            flux = min(C[t[x]][x] - F[t[x]][x], flux);
        sol += flux * dist[d];
        for (int x = d; x; x = t[x]) {
            F[t[x]][x] += flux;
            F[x][t[x]] -= flux;
        }
    }
    fout << sol;
    fout.close();
}