#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#define pb push_back
#define mp make_pair
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("traseu.in");
ofstream g("traseu.out");
int i,n,fluxm,m,sol,dest,x,y,cc,gre[70],gri[70],c[70][70],d[70],viz[70],t[70];
vector<pair<int,int> >l[66];
queue<int>q;
inline bool bfs()
{
    memset(d,INF,sizeof(d));
    memset(viz,0,sizeof(viz));
    memset(t,0,sizeof(t));
    int y,cost;
    q.push(0);
    viz[0]=1;
    d[0]=0;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        viz[x]=0;
        for(int i=0,dim=l[x].size();i<dim;++i)
        {
            y=l[x][i].first;
            cost=l[x][i].second;
            if(d[y]>d[x]+cost&&c[x][y]>0)
            {
                d[y]=d[x]+cost;
                t[y]=x;
                if(!viz[y])
                {
                    viz[y]=1;
                    q.push(y);
                }
            }
        }
    }
    return d[dest]==INF;
}
int main()
{
    f>>n>>m;
    dest=n+1;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>cc;
        l[x].pb(mp(y,cc));
        l[y].pb(mp(x,-cc));
        ++gre[x];
        ++gri[y];
        c[x][y]=INF;
        sol+=cc;
    }
    for(i=1;i<=n;++i)
    {
        if(gri[i]>gre[i])
        {
            l[0].pb(mp(i,0));
            l[i].pb(mp(0,0));
            c[0][i]=gri[i]-gre[i];
        }
        else
        if(gri[i]<gre[i])
        {
            l[dest].pb(mp(i,0));
            l[i].pb(mp(dest,0));
            c[i][dest]=gre[i]-gri[i];
        }
    }
    while(1)
    {
        if(bfs())
        break;
        fluxm=INF;
        x=dest;
        while(x)
        {
            fluxm=min(fluxm,c[t[x]][x]);
            x=t[x];
        }
        if(!fluxm)
        continue;
        x=dest;
        while(x)
        {
            c[t[x]][x]-=fluxm;
            c[x][t[x]]+=fluxm;
            x=t[x];
        }
        sol+=fluxm*d[dest];
    }
    g<<sol<<'\n';
    return 0;
}