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

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

const int MAX_N = 70;
const int INF = 0x3f3f3f3f;

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() {
    memset(d, INF, sizeof(d));
    memset(dad, 0, sizeof(dad));
    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() {
    int n, m;
    fin >> n >> m;
    D = n + 1;

    int ans = 0;
    for(int i = 1; i <= m; i++) {
        int a, b, cs;
        fin >> a >> b >> cs;
        
        in[b]++;
        out[a]++;
        ans += cs;

        c[a][b] = INF;
        cost[a][b] = cs;
        cost[b][a] = -cs;
        
        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;
}