// https://www.infoarena.ro/problema/hamilton

#include<fstream>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m, G[19][19];
int costMinim = -1; // costul minim gasit, initializat cu -1
int v[19]; // vector ce memoreaza ciclul hamiltonan

void citire() {
	fin >> n >> m;

	int x, y, cost;

	for(int i = 0; i < m; i++) {
		fin >> x >> y >> cost;

		G[x][y] = cost;
	}
}

bool valid(int kNou) {
	// verific daca v[k] este o alegere valida

	if(!G[v[kNou-1]][v[kNou]]) {
		// nu exista muchie intre ultimul nod valid si nodul ce se verifica
		return false;
	}

	for(int i = 0; i < kNou; i++) {
		if(v[i] == v[kNou]) {
			// nodul a fost deja pus
			return false;
		}
	}

	return true;
}

void BT(int k, int costCurent) {
	if(k == n - 1) {
		// am ajuns la final. Mai trebuie sa ma intorc in primul nod, pentru a incheia ciclul
		int costInchidereCiclu = G[v[k]][v[0]];

		if(!costInchidereCiclu) {
			return;
		}

		// verific daca pot corecta costul minim
		if(costMinim == -1 || costCurent + costInchidereCiclu < costMinim) {
			costMinim = costCurent + costInchidereCiclu;
		}

		return;
	}

	// iau toti vecinii lui v[k] si incerc sa obtin ciclu hamiltonian cu ajutorul lor
	for(int i = 0; i < n; i++) {
		v[k+1] = i;

		if(valid(k+1)) {
			int costNou = costCurent + G[v[k]][v[k+1]];
			if(costMinim == -1 || costNou < costMinim) {
				// daca depasesc costul minim deja cunoscut, atunci nu are rost sa mai inaintez cu recursivitatea
				BT(k+1, costNou);
			}
		}
	}
}

int main() {
	citire();

	v[0] = 0; // aleg ca prim nod al ciclului hamiltonian nodul 0

	BT(0, 0); // pornesc BT din nodul 1 (pot porni din orice nod, fiindca ciclul hamiltonian oricum trece prin toate nodurile)

	if(costMinim == 0) {
		fout << "Nu exista solutie" << endl;
	} else {
		fout << costMinim << endl;
	}

	fin.close();
	fout.close();

	return 0;
}