#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f ("hamilton.in");
ofstream g ("hamilton.out");

const int INF = 0x3f3f3f;
const int NMAX = 18;
const int VALMAX = (1 << NMAX);

int n;
int graf[NMAX + 1][NMAX + 1];
int sol[VALMAX + 1][NMAX + 1];

void citeste() {
	int m, a, b, c;
	f >> n >> m;

	while (m--) {
		f >> a >> b >> c;
		graf[a][b] = c;
	}
}

int hamilton(int nod, int masca) {
	if (sol[masca][nod]) return sol[masca][nod];

	if (masca == (1 << n) - 1) {
		if (graf[nod][0] == 0)
			sol[masca][nod] = INF;
		else sol[masca][nod] = graf[nod][0];
		return sol[masca][nod];
	}

	int sol_crt = INF;
	for (int i = 1; i < n; i++) {
		if ((masca & (1 << i)) == 0 && graf[nod][i]) {
			int aux = hamilton(i, masca | (1 << i)) + graf[nod][i];
			sol_crt = min(sol_crt, aux);
		}
	}

	sol[masca][nod] = sol_crt;
	return sol_crt;
}

void rezolva() {
	int rez = hamilton(0, 1 << 0);
	if (rez == -1) g << "Nu exista solutie\n";
	else g << rez << '\n';
}

int main() {
	citeste();
	rezolva();
	return 0;
}