#include<fstream>
#include<vector>
#include<list>
#include<cstring>
#define pb push_back
#define DMAX 62
#define INF 0x3f3f3f
using namespace std;

ifstream fin ("traseu.in");
ofstream fout("traseu.out");
list<int> lista;
list<int>::iterator it;
vector< list<int> >l(DMAX,lista);
int i,n,m,x,y,flux,sol,grin[DMAX],grout[DMAX];
int d[DMAX],viz[DMAX],dad[DMAX],q[2*DMAX];
int cost[DMAX][DMAX],cap[DMAX][DMAX],flx[DMAX][DMAX];

int bf()
{
    int ls=0,ld=0,x,y,c;
    for(i=0;i<=n+1;++i)
        d[i]=INF;
    memset(viz,0,n+2);
    memset(dad,0,n+2);
    viz[0]=1;
    d[0]=0;
    q[0]=0;
    while(ls<=ld)
    {
        x=q[ls++];
        viz[x]=0;
        for(it=l[x].begin();it!=l[x].end();++it)
        {
            y=*it;
            c=cost[x][y];
            if(d[y]>d[x]+c && cap[x][y]>flx[x][y])
            {
                d[y]=d[x]+c;
                dad[y]=x;
                if(!viz[y])
                {
                    viz[y]=1;
                    q[++ld]=y;
                }
            }
        }
    }
    return d[n+1];
}

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y;
        fin>>cost[x][y];
        cost[y][x]=-cost[x][y];
        sol+=cost[x][y];
        cap[x][y]=INF;
        l[x].pb(y);
        l[y].pb(x);
        ++grin[x];
        ++grout[y];
    }
    for(i=1;i<=n;++i)
    {
        if(grin[i]<grout[i])
        {
            l[i].pb(0);
            l[0].pb(i);
            cap[0][i]=grout[i]-grin[i];
        }
        else if(grin[i]>grout[i])
        {
            l[i].pb(n+1);
            l[n+1].pb(i);
            cap[i][n+1]=grin[i]-grout[i];
        }
    }
    while(bf()!=INF)
    {
        flux=INF;
        for(i=n+1;i>0;i=dad[i])
            flux=flux>cap[dad[i]][i]-flx[dad[i]][i] ? cap[dad[i]][i]-flx[dad[i]][i] : flux;
        if(flux==INF)
            continue;
        for(i=n+1;i>0;i=dad[i])
        {
            flx[dad[i]][i]+=flux;
            flx[i][dad[i]]-=flux;
        }
        sol+=d[n+1]*flux;
    }
    fout<<sol;
    return 0;
}