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

using namespace std;

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

const int inf= 1<<30;
const int nmax= 61;

int n, m, s, d, sol= 0, sum= 0;

bool u[nmax+1];
int dist[nmax+1], p[nmax+1], in[nmax+1], out[nmax+1];
int c[nmax+1][nmax+1], cost[nmax+1][nmax+1], f[nmax+1][nmax+1];

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

bool bellmanford(  ) {
    for ( int i= 0; i<=n+1; ++i ) {
        dist[i]= inf;
        p[i]= u[i]= 0;
    }

    dist[s]= 0;
    u[s]= 1;
    for ( q.push(s); !q.empty(); q.pop() ) {
        int x= q.front();
        for ( vector <int>::iterator it= v[x].begin(); it!=v[x].end(); ++it ) {
            if ( c[x][*it]>f[x][*it] && dist[x]+cost[x][*it]<dist[*it] ) {
                dist[*it]= dist[x]+cost[x][*it];
                p[*it]= x;
                if ( u[*it]==0 ) {
                    u[*it]= 1;
                    q.push(*it);
                }
            }
        }
        u[x]= 0;
    }

    return dist[d]!=inf;
}

int fmcm(  ) {
    int ans= 0;
    while ( bellmanford() ) {
        int fmin= inf;
        for ( int i= d; i!=s; i= p[i] ) {
            fmin= min(fmin, c[p[i]][i]-f[p[i]][i]);
        }
        for ( int i= d; i!=s; i= p[i] ) {
            f[p[i]][i]+= fmin;
            f[i][p[i]]-= fmin;
        }

        ans= ans+fmin*dist[d];
    }

    return ans;
}

int main(  ) {
    fin>>n>>m;
    s= 0, d= n+1;
    for ( int cnt= 1, x, y, z; cnt<=m; ++cnt ) {
        fin>>x>>y>>z;
        v[x].push_back(y);
        v[y].push_back(x);
        ++out[x];
        ++in[y];

        c[x][y]= inf;
        cost[x][y]= z;
        cost[y][x]= -z;
        sum+= z;
    }

    for ( int i= 1; i<=n; ++i ) {
        if ( in[i]>out[i] ) {
            v[s].push_back(i);
            v[i].push_back(s);

            c[s][i]= in[i]-out[i];
            cost[s][i]= cost[i][s]= 0;
        }
        if ( in[i]<out[i] ) {
            v[i].push_back(d);
            v[d].push_back(i);

            c[i][d]= out[i]-in[i];
            cost[i][d]= cost[d][i]= 0;
        }
    }

    sol= fmcm();
    fout<<sol+sum<<"\n";

    return 0;
}