#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int NMAX = 19;
const int STATES = (1 << 18);
const int INF = 0x3f3f3f3f;
int N, M;
int costEdge[NMAX][NMAX], bestChain[STATES][NMAX];

inline int bit(int x) {
	return 1 << (x - 1);
}

void read() {
	scanf("%d%d", &N, &M);
	memset(costEdge, INF, sizeof(costEdge));
	int x, y, c;
	for (int edge = 0; edge < M; edge++) {
		scanf("%d%d%d", &x, &y, &c);
		x++; y++;
		costEdge[x][y] = min(costEdge[x][y], c);
	}
}

void solve() {
	memset(bestChain, INF, sizeof(bestChain));
	bestChain[bit(1)][1] = 0;
	for (int mask = 1; mask < (1 << N); mask++) {
		for (int lastNode = 1; lastNode <= N; lastNode++) {
			if (mask & bit(lastNode)) {
				for (int nextNode = 1; nextNode <= N; nextNode++) {
					if (!(mask & bit(nextNode))) {
						bestChain[mask ^ bit(nextNode)][nextNode] = min(
							bestChain[mask ^ bit(nextNode)][nextNode],
							bestChain[mask][lastNode] + costEdge[lastNode][nextNode]);
					}
				}
			}
		}
	}

	int result = INF, fullMask = bit(N + 1) - 1;
	for (int lastNode = 2; lastNode <= N; lastNode++) {
		result = min(result, bestChain[fullMask][lastNode] + costEdge[lastNode][1]);
	}

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

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

	read();
	solve();
	return 0;
}