#include <iostream.h>
#include <fstream.h>
#include <string.h>
int a[20][20],n,i,j,v[50],w[50],min=100,s,x,y,k,m,c;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
void citire(){
	f>>n>>m;
	for(i=1;i<=m;i++){
		f>>x>>y>>c;
//		a[y][x]=c;
		a[x][y]=c;
	}
}

void tipar(int k){
	s=0;
	if (a[v[n]][v[1]] == 0)
		return ;

	
	for(i=1;i<k;i++){
//		cout<<v[i]<<" ";
		s=s+a[v[i]][v[i+1]];
	}
//	cout<<v[1]<<" \n";
	s=s+a[v[n]][v[1]];
	if(s<min) {
		min=s;
		memcpy(w,v,sizeof(w));
	}
	
	
}
int cont(int k){
	if(a[v[k-1]][v[k]]==0)
		return 0;
	for(i=1;i<k;i++)
		if(v[i]==v[k])
			return 0;
	return 1;
}
void back(){
	v[1]=1;
	k=2;
	v[k]=1;
	while(k>1)
		if(v[k]<n){
			v[k]++;
			if(cont(k))
				if(k==n)
					tipar(k);
				else v[++k]=1;
		}else k--;
}

int main(){
	citire();
	back();
	g<<min;
	return 0;
	f.close();
	g.close();
}