/*
Ciclu hamiltonian de cost minim (fiecare nod este continut o singura data).
*/

#include <iostream>
#include <vector>
#include <stdio.h>
#include <limits.h>

#define MAXN	18
#define MAXC	500000
#define INF		100000000

#define min(a, b) (a < b ? a : b)

using namespace std;

int nr_noduri, nr_muchii, cost_min;
int cost[MAXN][MAXN], mat[MAXC][MAXN];
vector<int> graf[MAXN];

void calculeaza_cost () {
	int i, j, k, l;

	mat[1][0] = 0;
	cost_min = INF;

	for (i = 0; i < 1 << nr_noduri; i++)
		for (j = 0; j < nr_noduri; j++) 
			if (i && (1 << j))
				for (l = 0; l < (int)graf[j].size(); l++) {
					k = graf[j][l];
					if (i && (1 << k)) 
						mat[i][j] = min(mat[i][j], mat[i ^ (1 << j)][k] + cost[k][j]);
				}

	for (i = 0; i < (int)graf[0].size(); i++) {
		j = graf[0][i];
		cost_min = min(cost_min, mat[(1 << nr_noduri) - 1][j] + cost[j][0]);
	}
}

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

	int a, b, c, i, j;	
	for (i = 0; i < nr_noduri; i++)
		for (j = 0; j < nr_noduri; j++)
			cost[i][j] = INF;

	scanf("%d %d", &nr_noduri, &nr_muchii);
	for (i = 0; i < nr_muchii; i++) {
		scanf("%d %d %d", &a, &b, &c);
		graf[b].push_back(a);
		cost[a][b] = c;
	}

	for (i = 0; i < 1 << nr_noduri; i++)
		for (j = 0; j < nr_noduri; j++)
			mat[i][j] = INF;

	calculeaza_cost();

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

	return 0;
}