#include <cstdio>
#include <vector>
#include <cstring>
#define inf 0x3f3f3f3f
#define maxn 20
using namespace std;


int dp[1 << 19][maxn], cost[maxn][maxn], sol = inf;
vector <int> G[maxn];
int main ()
{

	freopen ("hamilton.in", "r", stdin);
	freopen ("hamilton.out", "w", stdout);

	int n, m, x, y, c ;
	scanf ("%d %d\n", &n, &m);

	while (m--) {

		scanf ("%d %d %d\n", &x, &y, &c);
		G[y].push_back (x);
		cost[x][y] = c;
	}
	
	for (int i = 0; i < 1 << n; i++)
		for (int bit = 0; bit < n; bit++)
			dp[i][bit] = inf;
	dp[1][0] = 0;
	
	for (int i = 1; i < 1 << n; i++)
		for (int bit = 0; bit < n; bit++)
			if (i & (1 << bit))
				for (int k = 0; k < G[bit].size (); k++)
					if (i & (1 << G[bit][k]))
						dp[i][bit] = min (dp[i ^ (1 << bit)][ G[bit][k] ] + cost[ G[bit][k] ][bit], dp[i][bit]);

	for (int i = 0; i < G[0].size (); i++)
		sol = min (sol, dp[(1 << n) - 1][ G[0][i] ] + cost[G[0][i]][0]);
	
	if (sol == inf) printf ("Nu exista solutie\n");
	else printf ("%d\n", sol);

	return 0;
}