#include <iostream>
#include <cstdio>
using namespace std;
const int oo = 1e8;
const int maxn = 18;

int len[1<<maxn-1][maxn-1];
int adjm[maxn][maxn];

int main() {
	for (auto& a: len) fill(begin(a), end(a), oo);
	for (auto& a: adjm) fill(begin(a), end(a), oo);
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adjm[u][v] = w;
	}
	int N = 1<<n-1;
	for (int i = 0; i < n-1; i++) {
		len[1<<i][i] = adjm[i][n-1];
	}
	for (int M = 1; M < N; M++) {
		for (int M1 = M; M1 != 0; M1 &= M1-1) {
			int i = __builtin_ctz(M1);
			int Mi = M^M1&-M1;
			for (int M2 = Mi; M2 != 0; M2 &= M2-1) {
				int j = __builtin_ctz(M2);
				len[M][i] = min(len[M][i], adjm[i][j]+len[Mi][j]);
			}
		}
	}
	int ans = oo;
	for (int i = 0; i < n-1; i++) {
		ans = min(ans, len[N-1][i]+adjm[n-1][i]);
	}
	if (ans == oo) {
		puts("Nu exista solutie");
	} else {
		printf("%d\n", ans);
	}
}