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

int main() {
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> adjm(n, vector<int>(n, oo));
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adjm[u][v] = w;
	}
	vector<vector<int>> lenpath(1<<n-1, vector<int>(n-1, oo));
	for (int i = 0; i < n-1; i++) {
		lenpath[1<<i][i] = adjm[i][n-1];
	}
	for (int mask = 1; mask < 1<<n-1; mask++) {
		for (int i = 0; i < n-1; i++) {
			if (!(mask&1<<i)) continue;
			for (int j = 0; j < n-1; j++) {
				if (!((mask^1<<i)&1<<j)) continue;
				lenpath[mask][i] = min(lenpath[mask][i],
						lenpath[mask^1<<i][j]+adjm[i][j]);
			}
		}
	}
	int ans = oo;
	for (int i = 0; i < n-1; i++) {
		ans = min(ans, lenpath[(1<<n-1)-1][i]+adjm[n-1][i]);
	}
	if (ans == oo) {
		puts("Nu exista solutie");
	} else {
		printf("%d\n", ans);
	}
}