#include <stdio.h>
#include <vector>
#include <queue>
#define Nmax 65
#define pb push_back
#define INF 2147000000
using namespace std;

vector< int > v[Nmax];
queue< int > Q;
int F[Nmax][Nmax],C[Nmax][Nmax],Cost[Nmax][Nmax];
int in[Nmax],out[Nmax],Dist[Nmax],prev[Nmax],inq[Nmax];
int n,m,ok,Rez,S,D;

inline int Minim(int x,int y){ return x<y ? x:y; }

void Flux(){
	int i,x,fmin; vector<int>:: iterator it;
	for(i=1;i<=n+1;++i) Dist[i]=INF, inq[i]=0;
	Q.push(0);
	
	while( ! Q.empty() ){
		x=Q.front(); Q.pop();
		inq[x]=0;
		
		for(it=v[x].begin(); it!=v[x].end(); ++it )
			if( C[x][*it] > F[x][*it] && Dist[*it] > Dist[x]+Cost[x][*it] ){
				Dist[*it] = Dist[x]+Cost[x][*it];
				prev[*it]=x;
				if( ! inq[*it] ){
					inq[*it]=1;
					Q.push(*it);
				}
			}
	}
	
	if( Dist[D] != INF ){
		fmin=INF;
		for(i=D; i!=S; i=prev[i])
			fmin=Minim(fmin,C[prev[i]][i]-F[prev[i]][i]);
		for(i=D; i!=S; i=prev[i]){
			F[prev[i]][i] += fmin;
			F[i][prev[i]] -= fmin;
		}
		ok=1;
		Rez += fmin * Dist[D];
	}
}

int main(){
	int i,j,k,x,y,z;
	vector< int >:: iterator it,it2;
	freopen("traseu.in","r",stdin);
	freopen("traseu.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		Cost[x][y]=z;
		out[x]++; in[y]++;
		Rez += z;
	}
	
	for(i=1;i<=n;++i) for(j=1;j<=n;++j)
		if( !Cost[i][j] ) Cost[i][j]=INF;
	
	for(k=1;k<=n;++k)
		for(i=1;i<=n;++i)
			for(j=1;j<=n;++j)
				if( Cost[i][k] != INF && Cost[k][j] != INF )
					Cost[i][j] = Minim(Cost[i][j],Cost[i][k]+Cost[k][j]);
	
	S=0; D=n+1;
	for(i=1;i<=n;++i){
		if( in[i] > out[i] ) v[S].pb(i),C[S][i]=in[i]-out[i];
		if( out[i] > in[i] ) v[i].pb(D),v[D].pb(i),C[i][D]=out[i]-in[i];
	}
	
	for(it=v[S].begin(); it!=v[S].end(); ++it)
		for(it2=v[D].begin(); it2!=v[D].end(); ++it2){
			C[*it][*it2]=INF, Cost[*it2][*it]=-Cost[*it][*it2];
			v[*it].pb(*it2); v[*it2].pb(*it);
		}
	
	v[D].clear();
	for(ok=1; ok; ){
		ok=0;
		Flux();
	}

	printf("%d\n",Rez);
	fclose(stdin); fclose(stdout);
	return 0;
}