#include <bits/stdc++.h>
#define BMAX (1<<18)+1
#define INF 1000000000
#define vi vector <int>
using namespace std;
 
int adj[20][20],dp[20][BMAX],n,m;
vi A[20];

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;
	}
	for(int i=0;i<n;i++){
		dp[i][1<<i]=0;
	}
	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<A[j].size();k++){
				if((i&(1<<A[j][k])) && j!=A[j][k] && adj[A[j][k]][j] && dp[A[j][k]][i^(1<<j)]!=-1 && dp[A[j][k]][i^(1<<j)]+adj[A[j][k]][j]<dp[j][i]){
					dp[j][i]=dp[A[j][k]][i^(1<<j)]+adj[A[j][k]][j];
				}
			}
		}
	}
	int s=INF;
	for(int i=0;i<20;i++){
		if(adj[i][0]){
			s=min(dp[i][(1<<n)-1]+adj[i][0],s);
		}
	}
	if(s==INF)s=0;
	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;
		A[a].push_back(b);
	}
	int h=hamilton();
	if(h)cout<<h;
	else cout<<"Nu exista solutie";
}