#include <stdio.h>
#include <string.h>

#define maxN 70
#define maxM 4000

struct nd{int v;nd*u;nd(){}nd(int pv,nd*pu){v=pv,u=pu;}};

int n,m,res,mat[maxN][maxN],in[maxN],out[maxN];
nd*lvec[maxN];
int st,cst,mst[maxN],viz[maxN],tt[maxN];
int outcys[maxM],outcye[maxM],koc;

void inputFunc(){
	FILE*fi=fopen("traseu.in","r");
	fscanf(fi,"%d %d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b,c;
		fscanf(fi,"%d %d %d",&a,&b,&c);a--,b--;
		lvec[a]=new nd(b,lvec[a]);
		mat[a][b]=c;
		in[b]++;out[a]++;
	}
	fclose(fi);
}

void outputFunc(){FILE*fi=fopen("traseu.out","w");fprintf(fi,"%d",res);fclose(fi);}

void roy(){
	for(int i=0;i<n;i++)for(int j=0;j<n;j++){
		int c=mat[i][j];
		for(int k=0;k<n;k++){
			int a=mat[i][k],b=mat[k][j];
			if(a && b && (!c || a+b<c))c=a+b;
		}
		mat[i][j]=c;
	}
}

int cycle(int c){
	if(c==st){
		if(viz[c])return 1;
	}else{
		if(viz[c] || mst[c])return 0;
	}
	
	viz[c]=1,mst[c]++;
	for(nd*i=lvec[c];i;i=i->u){
		cst+=mat[c][i->v];
		if(cycle(i->v))return 1;
		cst-=mat[c][i->v];
	}
	mst[c]--;
	return 0;
}
int cyc(int c){memset(viz,0,sizeof viz);st=c;return cycle(c);}


int ocycle(int c){
	if(viz[c])return -1;
	if(!viz[c] && mst[c])return c;
	
	viz[c]=1,mst[c]++;
	for(nd*i=lvec[c];i;i=i->u){
		cst+=mat[c][i->v];
		int ans=ocycle(i->v);
		if(ans!=-1)return ans;
		cst-=mat[c][i->v];
	}
	mst[c]--;
	return -1;
}
int ocyc(int c){
	memset(viz,0,sizeof viz);
	
	for(nd*i=lvec[c];i;i=i->u)if(!mst[i->v]){
		cst+=mat[c][i->v];
		int ans=ocycle(i->v);
		if(ans!=-1){
			outcys[koc]=c,outcye[koc++]=ans;
			return 1;
		}
		cst-=mat[c][i->v];
	}
	
	return 0;
}
int adition(){
	for(int i=0;i<n;i++)if(mst[i]){
		if(ocyc(i))return 1;
	}
	return 0;
}

int main(){
	inputFunc();
	roy();
	
	cyc(0);
	
	do{
		for(int i=0;i<n;i++)if(mst[i] && !tt[i]){
			int l=0;
			while(cyc(0))l=1;
			tt[i]=1;
			if(l)i=-1;
		}
	}while(adition());
	
	int min=1<<30;
	for(int i=0;i<n;i++){
		int s=0;
		for(int j=0;j<koc;j++){
			s+=mat[i][outcys[j]] + mat[outcye[j]][i];
		}
		if(min>s)min=s;
	}
	
	res=cst+min;
	outputFunc();
	return 0;
}