#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;
	}
	
	for (int j = 0; j < (1 << N); j++)
	for (int i = 0; i < N; i++) 
		if (j & (1 << i)) {
			X = j ^ (1 << i);
			for (int k = 0; k < N; k++) {
				if ((X & (1 << k)) && 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;
}