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

using namespace std;

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

const int nmax = 65;
const int inf = (1 << 30);
const int mmax = nmax * nmax;

struct str{
    int x, flux, cap, cost, op;

    str() {}
    str (int _x, int _cap, int _cost, int _op) {
        x = _x, cap = _cap, cost = _cost, op = _op, flux = 0;
    }
} v[mmax + 1];

int S, D, nrm;
int t[nmax + 1], intra[nmax + 1], d[nmax + 1], grad[nmax + 1];
bool viz[nmax + 1];

queue< int > q;
vector< int > g[nmax + 1];

inline void trage_muchie(int x, int y, int cap, int cost) {
    ++ nrm; v[ nrm ] = str(y, cap, cost, nrm + 1); g[ x ].push_back( nrm );
    ++ nrm; v[ nrm ] = str(x, 0, -cost, nrm - 1);  g[ y ].push_back( nrm );
}

bool bellman_ford() {
    for (int i = 1; i <= D; ++ i) {
        d[ i ] = inf, t[ i ] = -1, viz[ i ] = 0, intra[ i ] = 0;
    }
    while (!q.empty()) q.pop();

    q.push( S ); viz[ S ] = 1; t[ S ] = 0; d[ S ] = 0;

    while (!q.empty()) {
        int x = q.front(); q.pop();
        viz[ x ] = 0;

        for (auto i : g[ x ]) {
            if (d[ v[ i ].x ] > d[ x ] + v[ i ].cost && v[ i ].cap > v[ i ].flux) {
                d[ v[ i ].x ] = d[ x ] + v[ i ].cost;
                t[ v[ i ].x ] = x;
                intra[ v[ i ].x ] = i;

                if (viz[ v[ i ].x ] == 0) {
                    viz[ v[ i ].x ] = 1;
                    q.push(v[ i ].x);
                }
            }
        }
    }

    return (t[ D ] != -1);
}

int main() {
    int n, m;
    fin >> n >> m;

    S = n + 1; D = n + 2;
    int ans = 0;
    for (int i = 1; i <= m; ++ i) {
        int x, y, z;
        fin >> x >> y >> z;
        ans += z;

        trage_muchie(x, y, inf, z);
        ++ grad[ y ]; -- grad[ x ];
    }

    for (int i = 1; i <= n; ++ i) {
        if (grad[ i ] > 0) {
            trage_muchie(S, i, grad[ i ], 0);
        } else if (grad[ i ] < 0) {
            trage_muchie(i, D, -grad[ i ], 0);
        }
    }

    while (bellman_ford()) {
        int fluxmin = inf;
        for (int x = D; x != S; x = t[ x ]) {
            fluxmin = min(fluxmin, v[ intra[ x ] ].cap - v[ intra[ x ] ].flux);
        }

        ans += fluxmin * d[ D ];
        for (int x = D; x != S; x = t[ x ]) {
            v[ intra[ x ] ].flux += fluxmin;
            v[ v[ intra[ x ] ].op ].flux -= fluxmin;
        }
    }

    fout << ans << "\n";

    fin.close();
    fout.close();
    return 0;
}