#include <cstdio>
#include <vector>

using namespace std;

#define INF 1<<30

vector<int> arcs[20];
int cost[20][20];
int h[(1<<18) + 2][20];



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

	int n, m, x, y, co;
	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)
			h[i][j] = INF;


	for(int i=0; i<m; ++i) {
		scanf("%d%d%d", &x, &y, &co);
		arcs[y].push_back(x);
		cost[x][y] = co;
	}

	h[1][0] = 0;

	for(int i=0; i < 1<<n; ++i)
		for(int j=0; j<n; ++j)
			if (i & (1<<j))
				for(int k=0; k<arcs[j].size(); ++k)
					if (i & (1<<arcs[j][k])) {
						co = h[i ^ (1<<j)][arcs[j][k]] + cost[arcs[j][k]][j];
						if (co < h[i][j])
							h[i][j] = co;
					}
	x = INF;

	for(int i=0; i<arcs[0].size(); ++i) {
		co = h[(1<<n) - 1][arcs[0][i]] + cost[arcs[0][i]][0];
		if (co < x)
			x = co;
	}

	if (x == INF)
		printf("Nu exista solutie\n");
	else
		printf("%d\n", x);


	return 0;
}