#include<cstdio>
#include<vector>
using namespace std;
const int INF = 1000000000;
int N,M;
int sol[262500][20],cost[20][20];
vector<int> nr[20];
int main(){
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	int i,j,x,y,c;
	scanf("%d%d",&N,&M);
	for(i=0;i<M;++i){
		scanf("%d%d%d",&x,&y,&c);
		nr[y].push_back(x);
		cost[x][y]=c;
	}
	for(i=0;i<(1<<N);++i){
		for(j=0;j<N;++j)
			sol[i][j]=INF;
	}
	sol[1][0]=0;
	for(i=0;i<(1<<N);++i){
		for(j=0;j<N;++j){
			if(i & (1<<j) ){
				for(size_t k=0;k<nr[j].size();++k){
					if(i & (1<<nr[j][k]) )
						sol[i][j]=min(sol[i][j], sol[i^(1<<j)][nr[j][k]] + cost[nr[j][k]][j]);
				}
			}
		}
	}
	c=INF;
	for(size_t k =0; k<nr[0].size();++k){
		if(c>sol[(1<<N)-1][nr[0][k]] + cost[nr[0][k]][0])
			c=sol[(1<<N)-1][nr[0][k]] + cost[nr[0][k]][0];
	}
	printf("%d\n",c);
	fclose(stdin);
	fclose(stdout);
	return 0;
}