#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int N_MAX = 20;
const int X_MAX = 262150;
const int INF = 1000000000;

int N, M;
int Cost[N_MAX][N_MAX];
int C[X_MAX][N_MAX]; //in C[n][i] se retine costul unui lant ce se termina in i si contine nodurile coresp. bitilor lui n
vector<int> Inv_Edges[N_MAX];

int compute(int config, int last) {
	if (C[config][last] == -1) {
		C[config][last] = INF;
		for (auto x : Inv_Edges[last])	//parcurgem nodurile care se duc in last
			if (config & (1 << x)) { //alegem nodurile care apartin lantului
				if (x == 0 && config != (1 << last) + 1)	//nodul 0 il scoatem ultimul
					continue;
				C[config][last] = min(C[config][last], compute(config ^ (1 << last), x) + Cost[x][last]);
			}
	}
	return C[config][last];
}

int main() {
	in >> N >> M;

	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			Cost[i][j] = INF;
	for (int i = 0; i < X_MAX; ++i)
		for (int j = 0; j < N; ++j)
			C[i][j] = -1;
	C[1][0] = 0;

	int x = 0, y = 0;
	for (int i = 0; i < M; ++i) {
		in >> x >> y;
		in >> Cost[x][y];
		Inv_Edges[y].push_back(x);	//retinem arcul opus
	}

	//ciclul porneste din nodul 0
	int sol = INF;
	for (auto x : Inv_Edges[0])
		sol = min(sol, compute((1 << N) - 1, x) + Cost[x][0]);

	if (sol == INF)
		out << "Nu exista solutie\n";
	else out << sol << '\n';

	return 0;
}