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

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

const int N = 18, POW = (1 << N), oo = 2e9;

int cost[N][N], MIN[POW][N], n, m, sol = oo;
vector <int> g[N];

int min_cost (int bin, int x) {
	if (MIN[bin][x] == -1) {
		MIN[bin][x] = oo;
		for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
			if (bin & (1 << *it)) {
				if (!(*it) && (bin ^ (1 << x)) > 1)
					continue;
				MIN[bin][x] = min(MIN[bin][x], min_cost(bin ^ (1 << x), *it) + cost[*it][x]);
			}
	}
	return MIN[bin][x];
}			

int main() {
	fin >> n >> m;
	for (int i = 0; i < (1 << n); ++i)
		for (int j = 0; j < n; ++j)
			MIN[i][j] = -1;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cost[i][j] = oo;
	while (m--) {
		int x, y, c;
		fin >> x >> y >> c;
		cost[x][y] = c;
		g[y].push_back(x);
	}
	fin.close();
	MIN[1][0] = 0;
	for (vector <int> :: iterator it = g[0].begin(); it != g[0].end(); ++it)
		sol = min (sol, min_cost((1 << n) - 1, *it) + cost[*it][0]);
	if (sol < oo)
		fout << sol;
	else
		fout << "Nu exista solutie";
	fout.close();
}