#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");

const int N = 20;
const int inf = 1000000000;

int n, m, sol = inf;
int cost[N][N];
int c[1<<(N - 1)][N];
vector<int> v[N];

inline int min(const int &a, const int &b) {
	return a < b ? a : b;
}

int mem(int conf, int ln) {
	int i;
	
	if(c[conf][ln] == -1) {
		c[conf][ln] = inf;
		
		for(i = 0; i!=v[ln].size(); ++i) if(conf & (1<<v[ln][i])) {
			
			if(!v[ln][i] && conf != (1<<ln) + 1)
				continue;
			
			c[conf][ln] = min(c[conf][ln], mem(conf ^ (1<<ln), v[ln][i]) + cost[v[ln][i]][ln]);
		}
	}
	
	return c[conf][ln];
}

int main() {
	int i, j, a, b, cc;
	
	in >> n >> m;
	
	for(i = 0; i!=n; ++i)
		for(j = 0; j!=n; ++j)
			cost[i][j] = inf;
	
	for(i = 1; i<=m; ++i) {
		in >> a >> b >> cc;
		
		cost[a][b] = cc;
		v[b].push_back(a);
	}
	
	memset(c, -1, sizeof(c));
	
	c[1][0] = 0;
	
	for(i = 0; i!=v[0].size(); ++i)
		sol = min(sol, mem((1<<n) - 1, v[0][i]) + cost[v[0][i]][0]);
	
	if(sol == inf)
		out << "Nu exista solutie\n";
	else
		out << sol << "\n";
	
	return 0;
}