#include <stdio.h>
#include <math.h>

#define MAXN 2000000000

long n, m, i, x, y, c, cost[20][20], j, din[1000010][20], k;

inline long min(long a, long b) {
	if (a < b) return a;
	return b;
}

int main() {
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);
	
	scanf("%ld %ld", &n, &m);
	
	for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) cost[i][j] = MAXN;
	for (i = 1; i <= m; ++i) {
		scanf("%ld %ld %ld", &x, &y, &c);
		cost[x][y] = c;
	}
	
	long aux = 1 << n;
	for (i = 0; i < aux; ++i) for (j = 0; j <= n; ++j) din[i][j] = MAXN;
	
	din[1][0] = 0;
	for (i = 1; i < aux; ++i) {
		for (j = 0; j < n; ++j) {
			if( i != 1 && j == 0) continue;
			if (din[i][j] == MAXN) continue;
			for (k = 1; k < n; ++k) {
				if (!(i & (1 << k)) && cost[j][k] > 0) {
					din[(i | (1 << k))][k] = min(din[i][j] + cost[j][k], din[(i | (1 << k))][k]);
				}
			}
		}
	}
	
	long sol = MAXN;
	for (i = 1; i < n; ++i) {
		if( cost[i][0])
			sol = min(sol, din[aux - 1][i] + cost[i][0]);
	}
	if( sol != MAXN)
		printf("%ld\n", sol);
	else printf("Nu exista solutie");
	
	return 0;
}