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

#define NMax 70
#define inf 2100000000

ifstream f("traseu.in");
ofstream g("traseu.out");

int n,m,S,D;
vector<int> v[NMax];
int ant[NMax];
int C[NMax][NMax],F[NMax][NMax];
int Cost[NMax][NMax];

queue<int> cd;
bitset<NMax> B;
int d[NMax];

void Bellmanford()
{
    int i,s;
    while(!cd.empty())
    {
        s=cd.front(); cd.pop();
        B[s]=0;
        for(i=0;i<(int)v[s].size();i++) if(F[s][v[s][i]]<C[s][v[s][i]]) if(d[v[s][i]]>d[s]+Cost[s][v[s][i]])
        {
            ant[v[s][i]]=s;
            d[v[s][i]]=d[s]+Cost[s][v[s][i]];
            if(!B[v[s][i]]) cd.push(v[s][i]),B[v[s][i]]=1;
        }
    }
}

int Flux()
{
    for(int i=1;i<=n;i++) d[i]=inf,ant[i]=0;
    d[S]=0;

    cd.push(S);
    Bellmanford();

    if(d[D]==inf) return 0;

    int fmin=inf;
    int nod=D;
    while(ant[nod])
    {
        fmin=min(fmin,C[ant[nod]][nod]-F[ant[nod]][nod]);
        nod=ant[nod];
    }

    nod=D;
    while(ant[nod])
    {
        F[ant[nod]][nod]+=fmin;
        F[nod][ant[nod]]-=fmin;
        nod=ant[nod];
    }

    return fmin*d[D];
}

int gr[NMax];

int main()
{
    int i,a,b,c;

    f>>n>>m;

    S = n+1;
    D = n+2;

    int flux=0,cost=0;

    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        v[a].push_back(b);
        v[b].push_back(a);
        C[a][b]=inf;
        Cost[a][b]=c;
        Cost[b][a]=-c;
        flux += c;
        gr[a]--;
        gr[b]++;
    }

    for(i=1;i<=n;++i) if(gr[i]>0)
    {
        v[S].push_back(i);
        v[i].push_back(S);
        C[S][i] = gr[i];
    }
    else if(gr[i]<0)
    {
        v[i].push_back(D);
        v[D].push_back(i);
        C[i][D] = -gr[i];
    }

    n += 2;

    while(cost=Flux()) flux+=cost;

    g<<flux<<"\n";

    f.close();
    g.close();

    return 0;
}