#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;

const int NMAX = 20;
const int INF = 1000000000;

int N, M;
vector<int> G[NMAX];
int cost[NMAX][NMAX];
int C[1<<NMAX][NMAX];
int SOL = INF;

void citire()
{
	cin >> N >> M;
	int x, y, c;
	for(int i = 1 ; i <= M ; i++)
	{
		cin >> x >> y >> c;
		G[y].push_back(x);
		cost[x][y] = c;
	}
}

void init()
{
	for(int k = 1 ; k < (1<<N) ; k++)
		for(int i = 0 ; i < N ; i++)
			C[k][i] = INF;
		
	for(int i = 0 ; i < N ; i++)
		for(int j = 0 ; j < N ; j++)
			if(!cost[i][j])
				cost[i][j] = INF;
}

void rezolva()
{
	vector<int> :: iterator j;
	C[1][0] = 0;
	for(int k = 1 ; k < (1<<N) ; k++)
		for(int i = 1 ; i < N ; i++)
			if(k & (1<<i))
				for(j = G[i].begin(); j != G[i].end() ; j++)
					if(k & (1<<(*j)))
						C[k][i] = min(C[k][i], C[k - (1<<i)][*j] + cost[*j][i]);
					
	for(int i = 1 ; i < N ; i++)
		SOL = min(SOL, C[(1<<N) - 1][i] + cost[i][0]);
}

int main()
{
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);
	citire();
	init();
	rezolva();
	if(SOL != INF)
		printf("%d\n", SOL);
	else
		printf("Nu exista solutie");
	return 0;
}