// comis voiajor

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

#include<fstream>

using namespace std;

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

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

const int INF = 18 * 1000000 + 1; // un ciclu hamiltonian are n muchii

int costMinim = INF;
int cicluCostMinim[18];

int sol[19];
bool vizitat[18];

void generareCiclu(int nivel, int cost) {
	if(nivel == n) {
		// am adaugat in ciclu toate cele n noduri. Acum mai trebuie sa inchid ciclul
		if(graf[sol[nivel - 1]][0] > 0) {
			// pot inchide ciclul
			
			cost += graf[sol[nivel - 1]][0];

			// actualizez costul minim
			if(cost < costMinim) {
				costMinim = cost;
			}
		}
	} else {
		// continui sa construiesc ciclul
		for(int i = 0; i < n; i++) {
			if(graf[sol[nivel - 1]][i] > 0 && !vizitat[i]) {
				sol[nivel] = i;
				vizitat[i] = true;

				generareCiclu(nivel + 1, cost + graf[sol[nivel - 1]][i]);

				vizitat[i] = false;
			}
		}
	}
}

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

	for(int i = 0; i < m; i++) {
		int a, b, c;

		fin >> a >> b >> c;
		
		graf[a][b] = c;
	}

	sol[0] = 0;
	vizitat[0] = true;

	generareCiclu(1, 0);

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

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

	return 0;
}