#include <iostream>
#include <cstdio>

using namespace std;

#define maxN 19
#define inf (1 << 30)
#define maxNN (1 << 19)

int cost[maxN][maxN];
int sol[maxNN][maxN];


int main()
{
	freopen ("hamilton.in", "r", stdin);
	freopen ("hamilton.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N, &M);
	
	for (int i = 0; i <= N; ++ i)
		for (int j = 0; j <= N; ++ j) cost[i][j] = inf;
	for (int i = 0; i < (1 << N); ++ i)
		for (int j = 0; j <= N; ++ j) sol[i][j] = inf;
	
	while (M --)
	{
		int x, y, c;
		
		scanf ("%d %d %d", &x, &y, &c);
		
		cost[x][y] = c;
	}
	
	sol[1][0] = 0;
	
	for (int i = 0; i < (1 << N); ++ i)
		for (int j = 0; j < N; ++ j)
		{
			if (! (i & (1 << j))) continue;
			
			for (int bit = 0; bit < N; ++ bit)
			{
				if (! (i & (1 << bit))) continue;
				if (cost[bit][j] == inf) continue;
				if (bit == j) continue;
				
				sol[i][j] = min (sol[i][j], sol[i - (1 << j)][bit] + cost[bit][j]);
			}
		}
	
	int ans = inf;
	
	for (int i = 1; i <= N; ++ i) 
		if (sol[(1 << N) - 1][i] != inf) ans = min (ans, sol[(1 << N) - 1][i] + cost[i][0]);
	
	if (ans == inf) printf ("Nu exista solutie");
	else printf ("%d", ans);
	
	return 0;
}