#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

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

const int MAX_N = 70;
const int INF = 2000000000;

int rf[MAX_N][MAX_N];
int in[MAX_N], out[MAX_N];

int f[MAX_N][MAX_N];
int c[MAX_N][MAX_N];
int cost[MAX_N][MAX_N];

int S, D;

vector<int> A[MAX_N];

int d[MAX_N];
int dad[MAX_N];
bool inq[MAX_N];

int bellman() {
    for(int i = 0; i <= D; i++) {
        d[i] = INF;
        dad[i] = 0;
        inq[i] = false;
    }

    queue<int> Q;
    Q.push(S);
    inq[S] = true;
    d[S] = 0;

    while(!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        inq[nod] = false;
        if(nod == D) {
            continue;
        }
        
        for(auto it : A[nod]) {
            if(f[nod][it] < c[nod][it] && d[nod] + cost[nod][it] < d[it]) {
                d[it] = d[nod] + cost[nod][it];
                dad[it] = nod;
                if(!inq[it]) {
                    inq[nod] = true;
                    Q.push(it);
                }
            }
        }
    }
    return d[D];
}

int maxflow() {
    int fl = 0;
    int ans = 0;
    while(bellman() < INF) {
        int p = INF;
        for(int nod = D; nod != S; nod = dad[nod]) {
            p = min(p, c[dad[nod]][nod] - f[dad[nod]][nod]);
        }
        for(int nod = D; nod != S; nod = dad[nod]) {
            f[dad[nod]][nod] += p;
            f[nod][dad[nod]] -= p;
        }
        fl += p;
        ans += p * d[D];
    }
    return ans;
}

int main() {
    S = 0;
    D = 61;
    int n, m;
    fin >> n >> m;
    
    int ans = 0;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        rf[a][b] = c;
        in[b]++;
        out[a]++;
        ans += c;
        cost[a][b] = c;
        cost[b][a] = -c;
        A[a].push_back(b);
        A[b].push_back(a);
    }

    vector<int> st, dr;
    for(int i = 1; i <= n; i++) {
        if(in[i] > out[i]) {
            c[S][i] = in[i] - out[i];
            A[S].push_back(i);
            A[i].push_back(S);
        }
        else if(out[i] > in[i]) {
            c[i][D] = out[i] - in[i];
            A[i].push_back(D);
            A[D].push_back(i);
        }
    }
    
    fout << ans + maxflow();

    return 0;
}