#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 19
#define INF 0xFFFFFFF

int N, M, Cost[MAX][MAX], Best[MAX][(1<<18)+1], Pw[(1<<18)+1];
char Source[MAX][(1<<18)+1];

int main() {
	int X, Y, Z, C;

	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d %d %d", &X, &Y, &Z);
		Cost[X][Y] = Z;
	}
	
	for (int i = 0; i < N; i++) 
	for (int j = 0; j < (1 << N); j++){
		Best[i][j] = INF;
	}

	for (int i = 0; i < N; i++) {
		Best[i][1<<i] = 0;
		Source[i][1<<i] = i;
	}
	
	X = 1;
	for (int i = 0; i < N; i++) {
		Pw[X] = i;
		X *= 2;
	}

	int i, ii, k, kk;
	for (int j = 0; j < (1 << N); j++)
	{
		ii = j;
		while (ii > 0) {
			i = ii & (-ii);
			kk = j ^ i;
			ii -= i;
			i = Pw[i];
				X = kk;
				while (kk > 0) {
					k = kk & (-kk);
					kk -= k;
					k = Pw[k];
					if (Cost[k][i] > 0) {
						Z = Best[k][X] + Cost[k][i];
						if (Best[i][j] > Z) {
							Best[i][j] = Z;
							Source[i][j] = Source[k][X];
						}
					}
				}
		}
	}
	
	int Sol = INF;
	for (int i = 0; i < N; i++) 
	if (i != Source[i][(1<<N)-1] && Cost[i][Source[i][(1<<N)-1]] > 0) {
		Sol = min(Sol, Best[i][(1<<N)-1] + Cost[i][Source[i][(1<<N)-1]]);
	}
	
	if (Sol == INF) {
		printf("Nu exista solutie");
	} else {
		printf("%d\n", Sol);
	}
	
	return 0;
}