#include <stdio.h>
#define INF 20000000

namespace Var {
	FILE *fin, *fout;
	int N, M;
	int **C, **dp;
};

void citire() {
	using namespace Var;
	// Citire N, M
	fscanf(fin, "%d%d", &N, &M);
	
	// Alocare tablouri + initializare
	C = new int*[N]; dp = new int*[1 << N];
	for (int i = 0; i < N; ++i) {
		C[i] = new int[N];
		for (int j = 0; j < N; ++j) {
			C[i][j] = INF;
		}
	}
	for (int i = 0; i < (1 << N); ++i) {
		dp[i] = new int[N];
		for (int j = 0; j < N; ++j) {
			dp[i][j] = INF;
		}
	}
	dp[1][0] = 0;
	
	// Citire muchii
	for (int i = 0; i < M; ++i) {
		int x, y, c;
		fscanf(fin, "%d%d%d", &x, &y, &c);
		C[x][y] = c;
	}
}
void dinamica() {
	using namespace Var;
	for (int b = 3; b < (1 << N); b += 2) {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (((1 << i) | b) == b && ((1 << j) | b) == b && j != i) {
					int bp = b ^ (1 << i);
					int cand = dp[bp][j] + C[j][i];
					if (cand < dp[b][i]) {
						dp[b][i] = cand;
					}
				}
			}
		}
	}
}
void afisare() {
	using namespace Var;
	int mi = INF;
	for (int e = 1; e < N; ++e) {
		int cand = dp[(1 << N) - 1][e] + C[e][0];
		if (cand < mi) {
			mi = cand;
		}
	}
	if (mi == INF) {
		fprintf(fout, "Nu exista solutie");
	} else {
		fprintf(fout, "%d\n", mi);
	}
}

int main()
{
	using namespace Var;
	fin = fopen("hamilton.in", "r");
	fout = fopen("hamilton.out", "w");
	
	citire();
	dinamica();
	afisare();
	
	fclose(fin);
	fclose(fout);
	return 0;
}