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

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

int N,M,S,D,Rez;
int C[NMax][NMax],F[NMax][NMax],Cost[NMax][NMax],T[NMax],P[NMax],in[NMax],out[NMax];
vector<int> ad[NMax];

bool bellman()
{
	int x,i;
	static queue<int> qu;
	static bool b[NMax];

	memset(b,0,sizeof(b));
	memset(P,0,sizeof(P));
	memset(T,0x3f,sizeof(T));
	qu.push(S);T[S]=0;b[S]=true;

	while (!qu.empty())
	{
		x=qu.front();qu.pop();
		b[x]=false;
		for (i=0;i<(int)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 (!b[ad[x][i]]){
				b[ad[x][i]]=true;
				qu.push(ad[x][i]);
			}
		}
	}
	return T[D]!=oo;
}

int flux(){

	int ret=0,fmin,p;
	for (;bellman();){

		fmin=oo;
		for (p=D;p!=S;p=P[p])
			fmin=min(fmin,C[P[p]][p]-F[P[p]][p]);

		ret+=fmin*T[D];

		for (p=D;p!=S;p=P[p])
			F[P[p]][p]+=fmin;
			F[p][P[p]]-=fmin;
	}
	return ret;
}

int main()
{
	int i,x,y,c;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	S=N+1;D=N+2;
	for (i=1;i<=M;++i)
	{
		scanf("%d%d%d",&x,&y,&c);

		++out[x];++in[y];

		ad[x].push_back(y);
		ad[y].push_back(x);
		Cost[x][y]+=c;
		Cost[y][x]-=c;
		C[x][y]=oo;
		Rez+=c;
	}

	for (i=1;i<=N;++i)if (in[i]>out[i]){
		ad[S].push_back(i);
		ad[i].push_back(i);
		C[S][i]=in[i]-out[i];
	} else if (out[i]>in[i]){
		ad[D].push_back(i);
		ad[i].push_back(D);
		C[i][D]=out[i]-in[i];
	}

	Rez+=flux();
	freopen(OUT,"w",stdout);
	printf("%d\n",Rez);
	fclose(stdout);
	return 0;
}