#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];

void graf(vector<int> &st, vector<int> &dr) {
    S = 0;
    D =  61;
    for(auto it : st) {
        c[S][it] = in[it] - out[it];
        A[S].push_back(it);
        A[it].push_back(S);
    }
    for(auto it : dr) {
        c[it][D] = out[it] - in[it];
        A[it].push_back(D);
        A[D].push_back(it);
    }
    for(auto it : st) {
        for(auto it2 : dr) {
            if(!rf[it][it2]) {
                continue;
            }
            c[it][it2] = INF;
            cost[it][it2] = rf[it][it2];
            cost[it2][it] = -cost[it][it2];
            A[it].push_back(it2);
            A[it2].push_back(it);
        }
    }
}

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() {
    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;
    }

    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == j) {
                    continue;
                }
                if(rf[i][k] && rf[k][j] && (rf[i][k] + rf[k][j] < rf[i][j] || !rf[i][j])) {
                    rf[i][j] = rf[i][k] + rf[k][j];
                }
            }
        }
    }
    
    vector<int> st, dr;
    for(int i = 1; i <= n; i++) {
        if(in[i] > out[i]) {
            st.push_back(i);
        }
        else if(out[i] > in[i]) {
            dr.push_back(i);
        }
    }
    if(!st.size()) {
        fout << ans;
        return 0;
    }
    graf(st, dr);
    
    fout << ans + maxflow();

    return 0;
}