#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

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

#define nmax 18
#define inf 0x3f3f3f3f

int i, j, n, m;
int a, b, c;
int ans;

int cost[nmax][nmax];
int dp[nmax][(1 << nmax)];

struct nod {
	int u;
	nod *next;
};
nod *v[nmax];

void add(int i, int j) {
	nod *p = new nod;
	p->u = j;
	p->next = v[i];
	v[i] = p;
}

int main() {
	fin >> n >> m;
	memset(cost, inf, sizeof(cost));
	memset(dp, inf, sizeof(dp));
	for (i = 1; i <= m; ++i) {
		fin >> a >> b >> c;
		cost[a][b] = c;
		add(b, a);
	}
	int lim = (1 << n);
	dp[0][1] = 0;
	for (j = 1; j < lim; ++j) {
		for (i = 0; i < n; ++i) {
			if (j & (1 << i)) {
				for (nod *it = v[i]; it; it = it->next)
					if (j & (1 << it->u))
						dp[i][j] = min(dp[i][j], dp[it->u][j ^ (1 << i)] + cost[it->u][i]);
			}
		}
	}
	ans = inf;
	for (i = 0; i < n; ++i)
		ans = min(ans, dp[i][lim - 1] + cost[i][0]);
	if (ans < inf) fout << ans << '\n';
	else 
		fout << "Nu exista solutie\n";
	return 0;
}