#include<stdio.h>
long long int n,m,infinit,xx,yy,i,cc,c[62][62],pol[62],mm,cb,x[3600],y[3600],cost[3600];
void djikstra();
void muchii();
void swap(long long int i1,long long int i2);
void heapdown(long long int ic,long long int nc);
void fcm();
int main()
{
	FILE *f,*g;f=fopen("traseu.in","r");g=fopen("traseu.out","w");
	fscanf(f,"%lld%lld",&n,&m);
	infinit=2000000000;
	for(i=1;i<=m;i++){fscanf(f,"%lld%lld%lld",&xx,&yy,&cc);c[xx][yy]=cc;pol[xx]--;pol[yy]++;cb+=cc;}
	djikstra();
	muchii();
	for(i=mm/2;i>=1;i--)heapdown(i,mm);
	for(i=mm;i>=1;i--){swap(1,i);heapdown(1,i-1);}
	fcm();
	fprintf(g,"%lld\n",cb);
	fcloseall();
	return 0;
}
void djikstra()
{       long long int ii,jj,kk;
	for(ii=1;ii<=n;ii++)for(jj=1;jj<=n;jj++)if(!c[ii][jj]) c[ii][jj]=infinit;
	for(kk=1;kk<=n;kk++)for(ii=1;ii<=n;ii++)for(jj=1;jj<=n;jj++)if(c[ii][kk]+c[kk][jj]<c[ii][jj])c[ii][jj]=c[ii][kk]+c[kk][jj];
}
void muchii()
{       long long int ii,jj,ss=0,dd=0,s[62],d[62];
	for(ii=1;ii<=n;ii++)
	 { if(pol[ii]>0)
	    { ss++;s[ss]=ii;}
	   else
	    if(pol[ii]<0)
	    { dd++;d[dd]=ii;pol[ii]=-pol[ii];}
	 }
	for(ii=1;ii<=ss;ii++)
	 for(jj=1;jj<=dd;jj++)
	  if(c[s[ii]][d[jj]]<infinit)
	  { mm++;x[mm]=s[ii];y[mm]=d[jj];cost[mm]=c[s[ii]][d[jj]];}
}
void swap(long long int i1,long long int i2)
{       long long int aux;
	aux=x[i1];x[i1]=x[i2];x[i2]=aux;
	aux=y[i1];y[i1]=y[i2];y[i2]=aux;
	aux=cost[i1];cost[i1]=cost[i2];cost[i2]=aux;
}
void heapdown(long long int ic,long long int nc)
{
	long long int is,is1;
	is=2*ic;is1=2*ic+1;
	if(is>nc)return;
	if(is<nc) if(cost[is]<cost[is1])is=is1;
	if(cost[ic]<cost[is]){swap(is,ic);heapdown(is,nc);}
}
void fcm()
{       long long int poz=1,pp;
	while(poz<=mm)
	{
	   if(!pol[x[poz]]||!pol[y[poz]])poz++;
	   else
	   { cb+=cost[poz];pp=(pol[x[poz]]<pol[y[poz]])?pol[x[poz]]:pol[y[poz]];
	     pol[x[poz]]-=pp;pol[y[poz]]-=pp;poz++;
	   }
        }
}