#include<fstream>
#include<vector>
#include<queue>

using namespace std;
typedef int var;

ifstream fin("traseu.in");
ofstream fout("traseu.out");

const var MAXN = 60;
const var INF = 1000001;

#define src 0
#define sink (n+1)
#define nodes (n+1)


vector<var> G[MAXN];

var F[MAXN][MAXN], K[MAXN][MAXN], C[MAXN][MAXN], IND[MAXN], OUTD[MAXN];
//var src = 0, sink = n+1, nodes = n+1;
var n;

var COST[MAXN], PARENT[MAXN];
bool INQ[MAXN];

bool bellman() {
    for(var i=0; i<=nodes; i++) {
        COST[i] = INF;
        PARENT[i] = 0;
    }
    COST[src] = 0;

    queue<var> Q;

    Q.push(src);

    while(!Q.empty()) {
        var node = Q.front();
        Q.pop();
        INQ[node] = 0;
        for(vector<var>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
            var vec = *it;
            if(COST[vec] > COST[node] + K[node][vec] && F[node][vec] < C[node][vec]) {
                COST[vec] = COST[node] + K[node][vec];
                PARENT[vec] = node;
                if(!INQ[vec]) {
                    INQ[vec] = 1;
                    Q.push(vec);
                }
            }
        }
    }

    return PARENT[sink] != 0;
}


var mfmc() {
    var total = 0;

    while(bellman()) {
        var MIN = INF;
        for(var t=sink; t != src; t = PARENT[t])
            MIN = min(MIN, C[PARENT[t]][t] - F[PARENT[t]][t]);

        for(var t=sink; t != src; t = PARENT[t]) {

            F[PARENT[t]][t] += MIN;
            F[t][PARENT[t]] -= MIN;

            total += MIN * K[PARENT[t]][t];


        }
    }

    return total;
}

void AddEdge(var s, var d, var cap, var cost) {
    G[s].push_back(d);
    G[d].push_back(s);
    C[s][d] = cap;
    C[d][s] = 0;
    K[s][d] = cost;
    K[d][s] = -cost;
}

void build() {
    for(var i=1; i<=n; i++) {
        if(IND[i] > OUTD[i]) {
            AddEdge(src, i, IND[i] - OUTD[i], 0);
        } else if(OUTD[i] > IND[i]) {
            AddEdge(i, sink, OUTD[i] - IND[i], 0);
        }
    }
}

int main() {
    var m, a, b, c, flow = 0;
    fin>>n>>m;
    while(m--) {
        fin>>a>>b>>c;
        AddEdge(a, b, INF, c);
        flow += c;

        OUTD[a] ++;
        IND[b] ++;
    }
    build();

    flow += mfmc();

    fout<<flow;

}