#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define FIN "hamilton.in"
#define FOUT "hamilton.out"

#define MAXN 19
#define MAXC (1 << 18)
#define INF 2000000000

int N, M, R;
int D[MAXC][MAXN], A[MAXN][MAXN];

vector < pair <int, int> > V[MAXN];

int main()
{
	int i, j, k, x, y;
	pair <int, int> p;
	
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);
	
	scanf("%d%d", &N, &M);
	
	for (i = 1; i <= M; ++ i)
	{
		scanf("%d%d%d", &x, &y, &k);
		
		V[x].push_back(make_pair(y, k));
		A[x][y] = k;
	}
	
	for (i = 0; i < (1 << N); ++ i)
		for (j = 0; j < N; ++ j)
			D[i][j] = INF;
	
	D[1][0] = 0;
	for (i = 1; i < (1 << N) - 1; ++ i)
		for (j = 0; j < N; ++ j)
			if (D[i][j] != INF)
				for (k = 0; k < V[j].size(); ++ k)
					if ((i & (1 << V[j][k].first)) == 0)
					{
						p = V[j][k];
						D[i + (1 << p.first)][p.first] = min(D[i + (1 << p.first)][p.first], D[i][j] + p.second);
					}
	
	for (i = 1, R = INF; i < N; ++ i)
		if (D[(1 << N) - 1][i] != INF && A[i][0])
			R = min(R, D[(1 << N) - 1][i] + A[i][0]);
	
	if (R != INF)
		printf("%d\n", R);
	else
		printf("Nu exista solutie\n");
}