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