#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

#define file_in "traseu.in"
#define file_out "traseu.out"

#define inf 0x3f3f3f3f
#define nmax 666

int C[nmax][nmax];
int F[nmax][nmax];
vector< pair<int,int> > g[nmax];
int viz[nmax];
int n,m;
int in[nmax];
int out[nmax];
int s,d;
int tata[nmax];
int cost[nmax];


struct comp 
{
	bool operator()(int i,int j)
	{
		return cost[i]>cost[j];
	}
};
priority_queue<int,vector<int>,comp> q;


int dijkstra()
{
    vector< pair <int,int> > :: iterator it;
	int i,nod;
	for(i=1;i<=d;++i) cost[i]=inf;
	q.push(0);
	cost[0]=0;
	while(!q.empty())
	{
		nod=q.top();
		viz[nod]=0;
		q.pop();
		for(it=g[nod].begin();it!=g[nod].end();++it)
			if(C[nod][(it->first)]-F[nod][(it->first)]>0 && cost[(it->first)]>cost[nod]+(it->second))
			{
				cost[(it->first)]=cost[nod]+(it->second);
                tata[(it->first)]=nod;
				if(viz[(it->first)]!=1){
					q.push(it->first);
					viz[it->first]=1;
				}
			}
	}
	if(cost[d]<inf)
        return 1;
    return 0;
}


int main(){
	
	int i,a,b,c,sol,Vmin;
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	sol=0;
	scanf("%d %d", &n, &m);
	for (i=1;i<=m;++i){
		 scanf("%d %d %d", &a, &b, &c);
		 
		 g[a].push_back(make_pair(b,c));
		 g[b].push_back(make_pair(a,-c));
		 
		 in[b]++;
		 out[a]++;
		 
		 C[a][b]=0x3f3f3f3f;
		 sol+=c;
	}
	
	
	
	s=0;
	d=n+1;
	
	for (i=1;i<=n;++i)
		 if (in[i]>out[i]){
			 g[s].push_back(make_pair(i,0));
			 g[i].push_back(make_pair(s,0));
			 C[s][i]=in[i]-out[i];
		 }
		 else
		  if (in[i]<out[i]){
			 g[d].push_back(make_pair(i,0));
			 g[i].push_back(make_pair(d,0));
			 C[i][d]=out[i]-in[i];
		 }	 
		  
	memset(viz,0,sizeof(viz));	  
		  
	while(dijkstra())
    {
        int Vmin=inf;
        for(i=d;i!=s;i=tata[i])
            Vmin=min(Vmin,C[tata[i]][i]-F[tata[i]][i]);
        for(i=d;i!=s;i=tata[i])
        {
            F[tata[i]][i]+=Vmin;
            F[i][tata[i]]-=Vmin;
        }
        sol+=Vmin*cost[d];
	}
	  
	 
	printf("%d\n", sol);

	return 0;
	
}