// 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 timp: O(n!), deoarece exploram toate permutrile nodurilor grafului
// Complexitate spatiu: O(n^2), datorita matricei de adiacenta

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

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

struct NodBT{
	int nodCurent;
	int costCurent;
	int nodUrmator; // nodUrmator va memora nodurile adiacente cu nodul curent
};

NodBT stiva[18]; // memoreaza ciclul hamiltonian


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 nivel = 0;
	int costMinim = INF;
	
	// PUSH pe stiva cu nodul de start
	stiva[0].nodCurent = 0;
	stiva[0].nodUrmator = -1;
	stiva[0].costCurent = 0;

	vizitat[0] = true;
	
	while(nivel >= 0) {
		if(nivel == n - 1) {
			int nodCurent = stiva[nivel].nodCurent;
			int costCurent = stiva[nivel].costCurent;
			
			// am adaugat toate nodurile in permutare, mai trebuie doar sa inchid ciclul hamiltonian
			if(graf[nodCurent][0] != 0 && costCurent + graf[nodCurent][0] < costMinim) {
				costMinim = costCurent + graf[nodCurent][0];
			}

			vizitat[nodCurent] = false;

			nivel--; // POP stiva
		} else {
			stiva[nivel].nodUrmator++;

			// caut un nod adiacent nodului curent, care nu a mai fost vizitat
			while(stiva[nivel].nodUrmator < n) {
				if(graf[stiva[nivel].nodCurent][stiva[nivel].nodUrmator] > 0 && !vizitat[stiva[nivel].nodUrmator]) {
					break;
				}

				stiva[nivel].nodUrmator++;
			}

			if(stiva[nivel].nodUrmator < n) {
				stiva[nivel + 1].nodCurent = stiva[nivel].nodUrmator;
				stiva[nivel + 1].nodUrmator = -1;
				stiva[nivel + 1].costCurent = stiva[nivel].costCurent + graf[stiva[nivel].nodCurent][stiva[nivel].nodUrmator];

				vizitat[stiva[nivel].nodUrmator] = true;

				nivel++; // PUSH stiva
			} else {
				vizitat[stiva[nivel].nodCurent] = false;

				nivel--; // POP stiva
			}
		}
	}

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

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

	return 0;
}