#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
#define NMax 110
#define INF 0x3f3f3f3f
using namespace std;

const char IN[]="traseu.in",OUT[]="traseu.out";

int N,M,n,m,ct=1,Sol;
int Dist[NMax][NMax] , T[NMax] , P[NMax];
int C[NMax][NMax] , F[NMax][NMax] , Cost[NMax][NMax] , in[NMax] , out[NMax];
bool inQue[NMax];
vector<int> v[2];
vector<int> ad[NMax];

bool BellmanFord()
{
	int x,i;
	queue<int> qu;
	qu.push(0);
	
	memset(T,0x3f,sizeof(T));
	memset(P,0,sizeof(P));
	P[0]=-1;T[0]=0;
	while (!qu.empty())
	{
		x=qu.front();qu.pop();inQue[x]=false;
		
		for (i=0;i<ad[x].size();++i)
			if ( C[x][ad[x][i]]>F[x][ad[x][i]] && T[x]+Cost[x][ad[x][i]]<T[ad[x][i]])
		{
			T[ad[x][i]]=T[x]+Cost[x][ad[x][i]];P[ad[x][i]]=x;
			if (!inQue[ad[x][i]]){
				qu.push(ad[x][i]);
				inQue[ad[x][i]]=true;
			}
		}
	}
	return T[N+1]!=INF;
}

int flux()
{
	int i,ret=0;
	while (BellmanFord())
	{
		int fmin=INF;
		
		for (i=N+1;P[i]!=-1;i=P[i])
			fmin=min(fmin,C[P[i]][i]-F[P[i]][i]);
		
		if (!fmin) continue;
		
		for (i=N+1;P[i]!=-1;i=P[i])
		{
			F[P[i]][i]+=fmin;
			F[i][P[i]]-=fmin;
		}
		ret+=T[N+1]*fmin;
	}
	return ret;
}

int main()
{
	int l,i,j,x,y,c,m;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	memset(Dist,0x3f,sizeof(Dist));
	while (M--)
	{
		scanf("%d%d%d",&x,&y,&c);
		Dist[x][y]=c;
		++out[x];++in[y];
		Sol+=c;
		
		ad[x].push_back(y);
		ad[y].push_back(x);
		Cost[x][y]=c;
		Cost[y][x]=-c;
		C[x][y]=INF;
		
	}
	
	for (i=1;i<=N;++i)
		if ( in[i] > out[i])
			v[0].push_back(i),
			ad[0].push_back(i),C[0][i]=in[i]-out[i];
		else if (out[i]>in[i]) v[1].push_back(i),ad[i].push_back(N+1),C[i][N+1]=out[i]-in[i];
	
	freopen(OUT,"w",stdout);
	printf("%d\n",Sol+flux());
	fclose(stdout);
	
	return 0;
}