#include<stdio.h>
#include<stdlib.h>

#include<vector>
#include<string>
using namespace std;

#define MAXN 18
#define INFINIT 18000001

int M,N;
int A[MAXN][MAXN];

int costminim=INFINIT;
vector<int> L[MAXN];

int C[1<<MAXN][MAXN];

int X[MAXN];

void updatecost(int k){
	// X[0] ... X[k-1] contin indicii bitilor de 1
	int index=1,index1=1;
	for(int i=0;i<k;i++){
		index+=(1<<X[i]);
	}
	int u,v;
	for(int i=0;i<k;i++){
		// actualizez costul lantului care se termina in X[i]
		u=X[i]; C[index][u] = INFINIT;
		index1=1;
		for(int j=0;j<k;j++){
			if(j!=i)
				index1+=(1<<X[j]);
		}
		for(int j=0;j<k;j++){
			if(j==i)
				continue;
			v=X[j];
			if(A[v][u]){
				if(C[index1][v]){
					if(C[index][u] > (C[index1][v]+A[v][u]))
						C[index][u]=C[index1][v]+A[v][u];
				}
			}
		}
		if(C[index][u] == INFINIT)
			C[index][u] = 0;
	}
}


void combinari(int k,int i){
	if(i==k){ // o combinare completa
		updatecost(k);
		return;
	}
	int start=1;
	if(i>0) 
		start=X[i-1]+1; 
	for(int j=start;j<=(N-1);j++){
		X[i]=j; 
		combinari(k,i+1);
	}
}


void hamiltonian(){

	// trasee de 2 biti (o muchie 0-k)
	int index;
	for(int i=1;i<N;i++){
		index=(1<<i)+1;
		if(A[0][i])
			C[index][i]=A[0][i];
	}

	for(int k=2;k<N;k++){
		// trasee de k biti 
		combinari(k,0);
	}

	index=(1<<N)-1;
	for(int i=1;i<N;i++){
		if(C[index][i]>0 && A[i][0]){
			if((C[index][i]+A[i][0]) < costminim )
				costminim=C[index][i]+A[i][0];
		}
	}
}

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

	scanf("%d %d",&N,&M);

	int x,y,c;

	for(int i=0;i<M;i++){
		scanf("%d %d %d",&x,&y,&c);
		//L[y].push_back(x);
		A[x][y]=c;
	}

	hamiltonian();	

	if(costminim==INFINIT)
		printf("Nu exista solutie\n");
	else
		printf("%d\n",costminim);

	return 0;
}