#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX 20
#define INF 1<<30
#define min(a, b) (a < b ? a : b)
using namespace std;

int n, m, x, y, z, i, j, rez;
int C[1<<MAX][MAX], cost[MAX][MAX];
vector<int> l[MAX];

int func(int drum, int dest);

int main(){
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);
	rez = INF;
	scanf("%d%d", &n, &m);
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			cost[i][j] = INF;

	memset(C, -1, sizeof(C));
	C[1][0] = 0;
	for(i = 0; i < m; i++){
		scanf("%d%d%d", &x, &y, &z);
		l[y].push_back(x);
		cost[x][y] = z;
	}

	for(int i = 0; i < l[0].size(); i++)
		rez = min(rez, func((1<<n) - 1, l[0][i]) + cost[l[0][i]][0]);

	if(rez == INF)
		printf("Nu exista solutie");
	else
		printf("%d", rez);
	return 0;
}

int func(int drum, int dest){
	if(C[drum][dest] == -1){
		C[drum][dest] = INF;

		for(int i = 0; i < l[dest].size(); i++)
			if(drum & (1<<l[dest][i])){
				if(!l[dest][i] && drum != (1<<dest) + 1)
					continue;
				C[drum][dest] = min(C[drum][dest], func(drum ^ (1<<dest), l[dest][i]) + cost[l[dest][i]][dest]);
			}
	}

	return C[drum][dest];
}