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

#include<vector>
using namespace std;

#define MAXN 18
#define MAXCOST 18000001

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

int costminim=MAXCOST;
vector<int> L[MAXN];
bool vis[MAXN];

bool isok(int nod,int k){
	for(int i=0;i<(k-1);i++){
		if(X[i]==nod)
			return false;
	}
	return true;
}

void hamiltonian(int k,int cost){
	if(k==N){
		if(A[X[N-1]][X[0]]>0){
			cost+=A[X[N-1]][X[0]];
			if(cost<costminim)
				costminim=cost;
		}
		return;
	}

	vector<int>::iterator it;
	for(it=L[X[k-1]].begin();it!=L[X[k-1]].end();it++){
		if(!vis[*it]){
			vis[*it]=true;
			X[k]=*it;
			hamiltonian(k+1,cost+A[X[k-1]][*it]);
			vis[*it]=false;
		}
	}
}

int main(){
		
	freopen("hamilton.in", "r", stdin);
	//freopen("hamilton_test2.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[x].push_back(y);
		A[x][y]=c;
	}

	X[0]=0;
	hamiltonian(1,0);	

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

	return 0;
}