#include<cstdio>
#include<vector>
#include<queue>
#define Nmax 128
#define inf 0x3f3f3f3f
using namespace std;

int N,M,dist[Nmax][Nmax],g[Nmax],c[Nmax][Nmax],fm[Nmax][Nmax],cost[Nmax][Nmax],t[Nmax],v[Nmax],sol;
bool inQ[Nmax];

vector <int> a[Nmax];
queue  <int> q;

void init(){
	
	//de la sursa la nod
	for(int i=1;i<=N;++i)
		if(g[i] > 0){
			c[0][i]=g[i];
			a[i].push_back(0);
			a[0].push_back(i);			
		}
		
	//de la nod la destinatie
	for(int i=1;i<=N;++i)
		if(g[i] < 0){
			c[i][N+1]=-g[i];
			a[i].push_back(N+1);
			a[N+1].push_back(i);
		}
		
	//de la nod la nod
	for(int i=1;i<=N;++i)
		if(g[i] > 0 )
			for(int j=1;j<=N;++j)
				if(g[j] < 0 ){
					c[i][j]=inf;
					cost[i][j]=dist[i][j];
					cost[j][i]=-dist[i][j];
					a[i].push_back(j);
					a[j].push_back(i);
				}
}

bool bf(){
	
	memset(v,inf,sizeof(v));
	
	v[0]=0;
	q.push(0);
	inQ[0]=1;
	
	while(!q.empty()){
		
		
		int nod=q.front();
		q.pop();
		inQ[nod]=0;
		
		for(vector<int>::iterator it=a[nod].begin(); it!=a[nod].end(); ++it)
			
			if(v[*it] > v[nod] + cost[nod][*it] && fm[nod][*it] < c[nod][*it] ){
				
				v[*it] = v[nod] + cost[nod][*it];
				t[*it] = nod;
				
				if(!inQ[*it])
					inQ[*it]=1,
					q.push(*it);
							
		}
	}
	
	if(v[N+1]!=inf)
		return 1;
	return 0;
}

int main(){
	
	freopen("traseu.in","r",stdin);
	freopen("traseu.out","w",stdout);
	
	scanf("%d%d",&N,&M);
	
	memset(dist,inf,sizeof(dist));
	
	for(int i=1;i<=M;++i){
		int x,y,c;
		
		scanf("%d%d%d",&x,&y,&c);
		
		dist[x][y]=c;
		
		g[x]--;
		g[y]++;
		sol+=c;
	}
	
	for(int k=1;k<=N;++k)
		for(int i=1;i<=N;++i)
			for(int j=1;j<=N;++j)
				dist[i][j]=min(dist[i][j], dist[i][k] + dist[k][j] );
			
	init();
	
	while(bf()){
		
		int fmn=inf;
		
		for(int nod=N+1;nod!=0;nod=t[nod])
			fmn=min(fmn, c[t[nod]][nod] - fm[t[nod]][nod]);
		
		
		for(int nod=N+1;nod!=0;nod=t[nod])
			fm[t[nod]][nod]+=fmn,
			fm[nod][t[nod]]-=fmn;
			
		sol+=fmn*v[N+1];		
	}
	
	printf("%d\n",sol);
	
return 0;
}