#include <bits/stdc++.h>

using namespace std;

ifstream fin("traseu.in");
ofstream fout("traseu.out");
const int MAXV = 1e9 + 7;
struct Muchie {
    int y, c;
};
vector<Muchie> gr[62];
int n, m, i, j, flux[62][62];
int grdI[62], grdO[62];
int surs, dest, rasp;

int cost[62];
int pot[62];
int ant[62];

static inline bool Dijkastra() {
    for(int i = surs; i <= dest; i++) {
        cost[i] = MAXV;
        ant[i] = -1;
    }

    set<pair<int, int>> q;

    cost[surs] = 0;

    q.insert({cost[surs], surs});

    while(!q.empty()) {
        int nod = q.begin()->second;
        int costCur = q.begin()->first;
        q.erase(q.begin());

        if(cost[nod] < costCur) continue;

        for(Muchie urm : gr[nod]) {
            int costUrm = urm.c + cost[nod] - pot[urm.y] + pot[nod];
            if(costUrm < cost[urm.y] && flux[nod][urm.y] > 0) {
                cost[urm.y] = costUrm;
                ant[urm.y] = nod;
                q.insert({cost[urm.y], urm.y});
            }
        }
    }

    if(cost[dest] == MAXV) return false;
    for(int i = surs; i <= dest; i++) pot[i] += cost[i] - pot[surs];
    return true;
}

static inline void Reverse() {
    int nod = dest;
    int ma = MAXV;
    while(nod != surs) {
        ma = min(ma, flux[ant[nod]][nod]);
        nod = ant[nod];
    }

    nod = dest;
    while(nod != surs) {
        flux[ant[nod]][nod] -= ma;
        flux[nod][ant[nod]] += ma;
        nod = ant[nod];
    }
    rasp += cost[dest] * ma;
}

int main() {
    //ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> m;
    surs = 0;
    dest = n + 1;
    for(i = 1; i <= m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        gr[x].push_back(Muchie{y,  c});
        gr[y].push_back(Muchie{x, -c});

        flux[x][y] = MAXV;
        rasp += c;

        grdO[x]++;
        grdI[y]++;
    }

    for(i = 1; i <= n; i++) {
        if(grdI[i] > grdO[i]) {
            gr[surs].push_back(Muchie{i, 0});
            gr[i].push_back(Muchie{surs, 0});
            flux[surs][i] = grdI[i] - grdO[i];
        }
        else {
            gr[i].push_back(Muchie{dest, 0});
            gr[dest].push_back(Muchie{i, 0});
            flux[i][dest] = grdO[i] - grdI[i];
        }
    }

    while(Dijkastra()) Reverse();

    fout << rasp;

    return 0;
}