#include <bits/stdc++.h>
#define BMAX 1<<18+1
#define INF 400000010
using namespace std;

int adj[20][20],dp[20][BMAX],/*p[20][BMAX],*/n,m;

int hamilton(){
	memset(dp,-1,sizeof dp);
	for(int i=0;i<20;i++){
		for(int j=0;j<BMAX;j++)dp[i][j]=INF;
	}
//	memset(p,-1,sizeof p);
	for(int i=0;i<n;i++){
		dp[i][1<<i]=0;
		//p[i][1<<i]=i;
	}
	for(int i=1;i<(1<<n)+1;i++){
		for(int j=0;j<n;j++){
			if(i&(1<<j))
			for(int k=0;k<n;k++){
				if(j!=k && adj[k][j] && dp[k][i^(1<<j)]!=-1 && dp[k][i^(1<<j)]+adj[k][j]<dp[j][i]){
					dp[j][i]=dp[k][i^(1<<j)]+adj[k][j];
				//	p[j][i]=p[k][i^(1<<j)];
				}
			}
		}
	}
	int s=INF;
	for(int i=0;i<n;i++){
		//if(dp[i][(1<<n)-1] && adj[i][p[i][(1<<n)-1]]){
			s=min(dp[i][(1<<n)-1],s);//+adj[i][p[i][(1<<n)-1]],s);
		//}
	}
	return s;
}

int main(){
	ifstream cin("hamilton.in");
	ofstream cout("hamilton.out");
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		if(adj[a][b]!=0)adj[a][b]=min(c,adj[a][b]);
		else adj[a][b]=c;
	}
	int h=hamilton();
	if(h==INF)cout<<h;
	else cout<<"Nu exista solutie";
}