#include<stdio.h>
#include<vector>
using namespace std;
vector<int> v[ 20 ];
int c[20][20],x[ 20 ],i,j,k,l,m,n,sol = 1<<30;
bool viz[20];
int a,b,C;
void back(int k,int cost){
if(k == n){
	if(c[x[n]][x[1]])
		if(cost + c[x[n]][x[1]] < sol)
			sol = cost + c[x[n]][x[1]];
	return;
}

int i,n,X;
n = v[x[k]].size();
for(i = 0; i < n ; i++){
	X = v[x[k]][i];
	if(!viz[X])
		{viz[X] = true;
		x[k+1] = X;
		back(k+1,cost + c[x[k]][X]);
		viz[X] = false;
		}
}
}


int main(){
freopen("hamilton.in","r",stdin);
freopen("hamilton.out","w",stdout);

scanf("%d %d" ,&n,&m);

for(i = 1 ; i<= m ; i++)
	{scanf("%d %d %d",&a,&b,&C);
	v[a].push_back(b);
	c[a][b] = C;
	}
viz[0] = true;
back(1,0);
printf("%d",sol);
return 0;}