#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<deque>
#include<queue>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int mx=18;
const int inf=1e9;

int n,m,cost[mx][mx],dp[1<<18][mx];

bool contains(int path,int element){
	return path&(1<<element);
}
int without(int path,int element){
	return path^(1<<element);
}

void read(){
	fin>>n>>m;
	int a,b,c;

	for(int i=0;i<mx;i++){
		for(int k=0;k<mx;k++){
			if(i!=k)
				cost[i][k]=inf;
		}
	}

	for(int i=0;i<m;i++){
		fin>>a>>b>>c;
		cost[a][b]=c;
	}
}


void solve(){
	int max=1<<n,mask=(1<<n)-1;

	for(int i=0;i<max;i++){
		for(int j=0;j<n;j++){
			dp[i][j]=inf;
		}
	}
	dp[1][0]=0;

	for(int i=0;i<=max;i++){
		for(int j=0;j<n;j++){

			if(contains(i,j)){

				for(int k=0;k<n;k++){
					int less=without(i,j);

					if(j!=k && contains(i,k)){
						dp[i][j]=min(dp[i][j],dp[less][k]+cost[k][j]);
					}

				}
			} 
		}	
	}

	int result=inf;
	for(int j=1;j<n;j++){
		result=min(result,dp[mask][j]+cost[j][0]);
	}
	if(result==inf){
		fout<<"Nu exista solutie";
	}
	else fout<<result;
}

int main(){
	read();
	solve();
	return 0;
}