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

#define maxN 70

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

int n,m,gs,res,mat[maxN][maxN],gr[maxN];
nd*lvec[maxN];
int k,l,dis[maxN][maxN],comp[maxN],wei[maxN],who[maxN];
int st[maxN],eu[maxN],seu,sum;

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;gs+=c;
		gr[a]++,gr[b]--;
	}
	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;
	}
}

void back(int lvl){
	if(lvl==k){
		if(res>sum)res=sum;return;
	}
	if(sum+eu[lvl]>=res)return;
	int&i=st[lvl];
	if(!lvl)i=0;else{
		if(comp[lvl-1]==comp[lvl])i=st[lvl-1];else i=0;
	}
	for(;i<l;i++)if(wei[i]){
		wei[i]--;sum+=dis[lvl][i];
		
		back(lvl+1);
		
		wei[i]++;sum-=dis[lvl][i];
	}
	
}

void eur(int lvl){
	if(lvl<0){
		res=sum;return;
	}
	int min=999999999,mp,min2=min;
	for(int i=0;i<l;i++){
		if(wei[i])if(min>dis[lvl][i])min=dis[lvl][i],mp=i;
		if(min2>dis[lvl][i])min2=dis[lvl][i];
	}
	seu+=min2;
	eu[lvl]=seu;
	
	wei[mp]--,sum+=min;
	eur(lvl-1);
	sum-=min,wei[mp]++;
	
	
}

int main(){
	inputFunc();
	roy();roy();
	for(int i=0;i<n;i++)if(gr[i]<0){
		who[l]=i;wei[l++]=-gr[i];
	}
	for(int i=0;i<n;i++){
		int c=gr[i]+1;
		while(c--,c>0){
			for(int j=0;j<l;j++){
				dis[k][j]=mat[who[j]][i];
			}
			comp[k++]=i;
		}
	}
	
	eur(k-1);
	back(0);
	res+=gs;
	outputFunc();
	return 0;
}