#include <fstream>
#define DIM 18
#define INF 2000000001
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n, m, x, y, cost, nr, mini, c[DIM][DIM], d[1 << DIM][DIM];
int main() {
	fin >> n >> m;
	while (m--) {
		fin >> x >> y >> cost;
		c[x][y] = cost;
	}
	nr = (1 << n) - 1;
	for (int i = 1; i <= nr; i++)
		for (int j = 0; j < n; j++)
			d[i][j] = INF;
	d[1][0] = 0;
	for (int st = 1; st <= nr; st++)
		for (int i = 0; i < n; i++)
			if (st & (1 << i))
				for (int j = 0; j < n; j++)
					if (c[i][j] != 0 && !(st & (1 << j))) {
						int nxt = st + (1 << j);
						d[nxt][j] = min(d[nxt][j], d[st][i] + c[i][j]);
					}
	mini = INF;
	for (int i = 1; i < n; i++)
		if (c[i][0] != 0)
			mini = min(mini, d[nr][i] + c[i][0]);
	if (mini == INF)
		fout << "Nu exista solutie";
	else
		fout << mini;
	return 0;
}