#include <iostream>

using namespace std;

#define maxN 20
#define maxConf (1 << 19)
#define inf (1 << 28)

int cost[maxN][maxN], sol[maxConf][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;
	
	
	for (int i = 1; i <= M; ++ i)
	{
		int x, y, c;
		
		scanf ("%d %d %d", &x, &y, &c);
		
		cost[x][y] = c;
	}
	
	
	sol[1][0] = 0;

	
	for (int conf = 0; conf < (1 << N); ++ conf)
		for (int i = 0; i < N; ++ i)
		{
			if (! (conf & (1 << i) ) ) continue;
			
			for (int bit = 0; bit < N; ++ bit)
			{
				if ( ! ( conf & (1 << bit) ) ) continue;
				if (cost[bit][i] == inf) continue;
				if (bit == i) continue;
				
				sol[conf][i] = min ( sol[conf][i], sol[conf - (1 << i)][bit] + cost[bit][i] );
			}
		}
	
	
	int rsp = inf;
	
	for (int i = 0; i < N; ++ i)
		if (sol[(1 << N) - 1][i] != inf) rsp = min (rsp, sol[(1 << N) - 1][i] + cost[i][0]);
	
	
	if (rsp == inf) printf ("Nu exista solutie");
	else printf ("%d", rsp);
	
	
	return 0;
}