#include<stdio.h>
#include<vector>
#include<deque>
#include<utility>
#include<assert.h>
using namespace std;

#define NMAX 64
#define inf 0x3f3f3f3f

int N,M;
vector< pair<int,int> > G[NMAX];
int Cap[NMAX][NMAX],F[NMAX][NMAX];
int C[NMAX][NMAX];
int ans;
bool viz[NMAX];
int P[NMAX],D[NMAX],Gr[NMAX];

int BF( int source, int dest )
{
	int i;
	for(i=source; i<=dest; ++i)
	{
		viz[i]=0,P[i]=0,D[i]=inf;
	}
	
	deque< int > Deq;
	
	D[source]=0;
	Deq.push_front(source);
	viz[source]=1;
	
	int nod,v,cost;
	unsigned it;
	
	while( !Deq.empty() )
	{
		nod=Deq.front();
		Deq.pop_front();
		viz[nod]=0;
		
		//printf("\n nod %d \n",nod);
		
		for( it=0; it!=G[nod].size(); ++it )
		{
			v=G[nod][it].first;
			cost=G[nod][it].second;
			
		//	printf("vecin %d\n",v);
		//	printf("%d %d\n",Cap[nod][v],F[nod][v]);
			fflush(stdout);
			//assert( Cap[nod][v]>=F[nod][v] );
			
			if( Cap[nod][v]==F[nod][v] )
				continue;
			
			if( D[nod]+cost < D[v] )
			{
				D[v]=D[nod]+cost;
				P[v]=nod;
		//		printf("Noua val D[%d] %d\n",v,D[v]);
				
				if( !viz[v] )
				{
					Deq.push_back(v);
					viz[v]=1;
				}
			}
		}
	}
	
	if( D[dest]==inf )	
		return 0;

	int flow=inf;nod=dest;			
	while( nod!=source )
	{
		v=P[nod];
		flow=min(flow,Cap[v][nod]-F[v][nod]); 
		nod=v;
	}
		
	nod=dest;
	while( nod!=source )
	{
		v=P[nod];
		F[v][nod]+=flow;
		F[nod][v]-=flow;
		nod=v;
	}
	
	ans+=D[dest]*flow;
	//printf("%d\n",flow);
	return flow;
}

void RF()
{
	int i,j,k;
	for(k=1; k<=N; ++k)
		for(i=1; i<=N; ++i)
			for(j=1; j<=N; ++j)
				if( i!=j && i!=k && k!=j )
				C[i][j]=min( C[i][j], C[i][k]+C[k][j] );
	
	/*
	for(i=1; i<=N; ++i)
	{
		for(j=1; j<=N; ++j)
			printf("%d ",C[i][j]);
	printf("\n");
	}*/
}

void init()
{
	int i,j;
	for(i=1; i<=N; ++i)
		for(j=1; j<=N; ++j)
			if( i!=j )
				C[i][j]=inf;
}

void read()
{
	int i;
	int a1,a2,a3;
	
	for(i=1; i<=M; ++i)
	{
		scanf("%d %d %d\n",&a1,&a2,&a3);
		G[a1].push_back(make_pair(a2,a3));	
		//G[a2].push_back(make_pair(a1,-a3));
		
		C[a1][a2]=min(C[a1][a2],a3);
		
		ans+=a3;
		--Gr[a1];
		++Gr[a2];
	}
}

void virtual_graph()
{
	int i,j;
	int source=0;
	int dest=N+1;
	
	for(i=1; i<=N; ++i)
	{
		if( Gr[i]>0 )
		{
			G[0].push_back(make_pair(i,0));
			G[i].push_back(make_pair(0,0));
			Cap[0][i]=Gr[i];
			
			
			for(j=1; j<=N; ++j)
				if( Gr[j]<0 )
				{
					Cap[i][j]=inf;
					C[j][i]=-C[i][j];
					G[i].push_back(make_pair(j,C[i][j]));
					G[j].push_back(make_pair(i,C[j][i]));
				}
		}	
		if( Gr[i]<0 )
		{
			G[i].push_back(make_pair(dest,0));
			Cap[i][dest]=-Gr[i];
		}	
	}

	/*
		Run flow on it 
	*/
	while( BF(source,dest) );
}


int main()
{
	freopen("traseu.in","r",stdin);
	freopen("traseu.out","w",stdout);
	
	scanf("%d%d",&N,&M);

	init();
	read();
	RF();
	virtual_graph();

	printf("%d\n",ans);
	
	return 0;
}