#include <stdio.h>
#include <vector>

using namespace std;

#define NMAX 64
#define INF 0x3f3f3f3f
#define pb push_back
#define sz size()

vector<int> G[NMAX];

long int n,m,c[NMAX][NMAX];
long int f[NMAX][NMAX],cst[NMAX][NMAX];
long int gin[NMAX],gout[NMAX],sol;
long int cd[NMAX],cd2[NMAX],TT[NMAX],d[NMAX],viz[NMAX];

long int bf()
{
	long int i,j,nod;

	for (i=1;i<=n+1;i++)
		d[i]=INF;
	d[0]=0;

	cd[ cd[0]=1 ] = 0;
	
	while (cd[0])
	{
		memset(cd2,0,sizeof(cd2));
                memset(viz,0,sizeof(viz));
                
		for (i=1;i<=cd[0];i++)
			{
			nod=cd[i];
			for (j=0;j<G[nod].sz;j++)
				if ( (d[nod]+cst[nod][G[nod][j]]<d[G[nod][j]])&&(f[nod][G[nod][j]]<c[nod][G[nod][j]]) )
						{
						d[ G[nod][j] ] = d[nod]+ cst[nod][G[nod][j]];
						TT[ G[nod][j] ] = nod;
						if (!viz[ G[nod][j] ])
                                                        {
                                                        cd2[ ++cd2[0] ] = G[nod][j];
                                                        viz[ G[nod][j] ] = 1;
                                                        }
						}
			}

		for (i=0;i<=cd2[0];i++)
			cd[i]=cd2[i];
	}
	if (d[n+1]==INF) return 0;
	return 1;
}

int main()
{
	freopen("traseu.in","r",stdin);
	freopen("traseu.out","w",stdout);

	scanf("%ld %ld",&n,&m);

	long int i,x,y,ct;

	for (i=1;i<=m;i++)
		{
		scanf("%ld %ld %ld",&x,&y,&ct);
		G[x].pb(y);
		G[y].pb(x);
		cst[x][y]=ct;
		cst[y][x]=-ct;
                c[x][y]=INF;
		gin[y]++;
		gout[x]++;
		sol+=ct;
		}

                
	for (i=1;i<=n;i++)
		if (gin[i]>gout[i]) {
                                     c[0][i]=gin[i] - gout[i];
                                     G[0].pb(i);
                                     }
			else {
                                c[i][n+1]=gout[i] - gin[i];
                                G[i].pb(n+1);
                                }


	long int nod,fmin;
        
	while ( bf() )
		{
		nod=n+1;
		fmin=INF;

		while (nod) 
			{
			fmin=min(fmin,c[ TT[nod] ][nod] - f[ TT[nod] ][nod] );
			nod=TT[nod];
			}
		
		sol=sol+fmin*d[n+1];

		nod=n+1;
		while (nod)
			{
			f[ TT[nod] ][nod]+=fmin;
			f[nod][ TT[nod] ]-=fmin;
                        nod=TT[nod];
			}
		}
	printf("%ld\n",sol);
	return 0;
}