#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];

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

	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;
	}

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