#include <bits/stdc++.h>
using namespace std;
const int nmax = 18;

vector<vector<pair<int,int>>> dx(nmax);
int dp[nmax][(1<<nmax)];

int main() {
	ifstream f("hamilton.in");
	ofstream g("hamilton.out");
	
	int n,m; f >> n >> m;
	for(int i=1; i<=m; i++) {
		int x,y,c; f >> x >> y >> c;
		dx[y].emplace_back(x,c);
	}
	
	for(int i=0; i<n; i++)
		for(int j=0; j<(1<<n); j++)
			dp[i][j] = 1e9;
	
	dp[0][1] = 0;
	for(int i=0; i<(1<<n); i++) { 
		for(int j=0; j<n; j++) {
			if(i&(1<<j)) {
				for(auto x : dx[j]) {
					dp[j][i] = min(dp[j][i], dp[x.first][i^(1<<j)] + x.second);
				}
			}
		}
	}
			
	int mn = 1e9;				
	for(auto i : dx[0])
		mn = min(mn, dp[i.first][(1<<n)-1] + i.second);
	if(mn!=1e9) g << mn;
	else g << "Nu exista solutie";
	return 0;
}