#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

#define INF 0x7f7f7f7f
#define maxN 70
#define maxK 400

int n,m,gs,res,mat[maxN][maxN],gr[maxN];
int k,l,dis[maxK][maxK];

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--;
		gs+=mat[a][b]=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 bellman(){
	queue<int> qu;
	int d[maxK],lst[maxK]={};
	memset(d,INF,sizeof d);
	d[0]=0;
	
	qu.push(0);
	while(!qu.empty()){
		int c=qu.front(); qu.pop();
		for(int i=0;i<=l;i++)if(dis[c][i]!=INF){
			int urm=d[c]+dis[c][i];
			if(urm<d[i]){
				d[i]=urm,lst[i]=c,qu.push(i);
			}
		}
		
	}
	
	int i=l;
	while(i){
		int a=lst[i],b=i;
		dis[b][a]=-dis[a][b];
		dis[a][b]=INF;
		i=a;
	}
	
	
	
	res+=d[l];
}

int main(){
	inputFunc();
	roy();roy();roy();
	
	for(int i=0;i<n;i++)if(gr[i]>0)k+=gr[i];
	l=2*k+1;
	
	memset(dis,INF,sizeof dis);
	int ik=1;
	for(int i=0;i<n;i++){
		int c=-gr[i]+1;
		while(c--,c>0){
			int jk=k+1;
			for(int j=0;j<n;j++){
				int c2=gr[j]+1;
				while(c2--,c2>0){
					dis[ik][jk]=mat[i][j];
					dis[jk++][l]=0;
				}
			}	
			dis[0][ik++]=0;
		}
	}
	
	for(int i=0;i<k;i++){
		bellman();
	}
	
	res+=gs;
	outputFunc();
	return 0;
}