#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int nmax = 20;
const int INF = 1e9+10;
const int nmax2 = (1 << 18)+10;
int n,m,mat[nmax][nmax],cost[nmax][nmax];
long int dp[nmax2][nmax];
void read_input(){
	fin >> n >> m;
	int nod_1,nod_2,costul;
	for(int i = 1; i <=m; i++){
		fin >> nod_1 >> nod_2 >> costul;
		mat[nod_1][nod_2] = 1;
		cost[nod_1][nod_2] = costul;
	}
};
void solve(){
   for(int i = 0; i < (1 << n); i++){
		for(int j = 0;j <n; j++){
		 dp[i][j] = INF;
		}
	}
	dp[1][0] = 0;
	for(int mask = 1;mask < (1 << n); mask++){
		for(int i = 0; i <n; i++){
			if(dp[mask][i] == INF) continue;
				for(int j = 0; j <n; j++){
					if(!(mask & (1 << j)) && mat[i][j]){
						dp[mask+(1 << j)][j] = min(dp[mask+(1 << j)][j],dp[mask][i] + cost[i][j]);
				}
			}
		}
	};
	long int ans = INF;
	for(int i = 1; i <n; i++){
		if(mat[i][0]){ans = min(ans,dp[(1 << n)-1][i] + cost[i][0]);}
	};
	if(ans == INF){fout << "Nu exista solutie";}else{
		fout << ans;
	}
}
int main(){
	read_input();
	solve();
	return 0;
}