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

#include<fstream>

using namespace std;

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

// INF ia valoarea maxima a unui arc dintre doua noduri, inmultita la numarul de arce dintr-un ciclu hamiltonian, la care adaugam 1
const int INF = 1000000 * 18 + 1;

// Descriere rezolvare:
// Problema comis-vorajorului se rezuma la a determina un ciclu hamiltonian de cost minim.
// Pentru a determina ciclul hamiltonian de cost minim, vom genera, 
// folosind metoda backtracking, toate ciclurile hamiltoniene.
// Un ciclu hamiltonian este un ciclu care cuprinde toate nodurile grafului o singura data.
// Asadar, problema se rezuma la generarea tuturor permutarilor nodurilor, astfel incat 
// intre oricare doua noduri vecine din permutarea generata sa exista un arc.
// Consider nodul 0 ca nod de start.
// (Cum ciclul hamiltonian trece prin toate nodurile, nu conteaza pe care nod il aleg pentru start.)
// Complexitate: O(n!)

int n, m;
int graf[18][18];

// vizitat[i] = true daca nodul i a fost vizitat
bool vizitat[18];

// Functia returneaza costul minim al unui drum Hamiltonian
// care porneste din nodul curent, viziteaza toate nodurile
// nevizitate exact o data si revine in nodul de start.
int BT(int pas, int nod) {
	if(pas == n - 1) {
		// avem n noduri in permutare, toate distincte, asadar avem toate nodurile 
		// in acest punct, tot ce trebuie sa mai facem este sa inchidem ciclul, cu un arc de la nodul curent la nodul de start
		if(graf[nod][0] == 0) {
			return INF;
		}

		return graf[nod][0];
	}

	vizitat[nod] = true;

	int costMinim = INF;

	// incerc extinderea drumului catre toate nodurile accesibile nevizitate
	for(int i = 0; i < n; i++) {
		if(graf[nod][i] > 0 && !vizitat[i]) {
			int cost = graf[nod][i] + BT(pas + 1, i);

			if(cost < costMinim) {
				costMinim = cost;
			}
		}
	}

	vizitat[nod] = false;

	// returnez costul minim al unui drum care porneste din nodul curent si ajunge in punctul de start al cicului hamiltonian
	return costMinim; 
}

int main() {
	fin >> n >> m;

	for(int i = 0; i < m; i++) {
		int a, b, c;
		fin >> a >> b >> c;
		graf[a][b] = c;
	}

	int costMinim = BT(0, 0);

	if(costMinim == INF) {
		fout << "Nu exista solutie\n";
	} else {
		fout << costMinim << "\n";
	}


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

	return 0;
}