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

#include<fstream>

using namespace std;

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

int n, m;
int G[19][19]; // matricea e initializata cu 0, fiind declarata global
int costMinim = -1; // costul minim gasit, initializat cu -1
int drum[19]; // vector ce memoreaza ciclul hamiltonan
int viz[19]; // viz[i] = 0 => nodul i nu a fost vizitat; viz[i] = 1 => nodul i a fost vizitat

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 drum[k] este o alegere valida

	if(viz[drum[kNou]]) {
		// nodul a fost deja vizitat
		return false;
	}

	if(!G[drum[kNou-1]][drum[kNou]]) {
		// nu exista arc intre ultimul nod valid si nodul ce se verifica
		// conform problemei, arcele au cost pozitiv
		// daca G[i][j] = 0, inseamna ca intre i si j nu exista arc
		return false;
	}

	return true;
}

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

		if(!costInchidereCiclu) {
			return;
		}

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

		return;
	}

	viz[drum[k]] = 1;

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

		if(valid(k+1)) {
			int costNou = costCurent + G[drum[k]][drum[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);
			}
		}
	}

	viz[drum[k]] = 0;
}

int main() {
	citire();

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

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

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

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

	return 0;
}