#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <cstring>

#define MAXX 20000000

using namespace std;
int matr[18][18], C[18][262144];
vector< vector<int> > vecs;

int calcul(int v, int q) {

	if (C[q][v] == -1) {
		C[q][v] = MAXX;
		for (unsigned int i = 0; i < vecs[q].size(); i++) {
			if (v & (1 << vecs[q][i])) {
				C[q][v] = min(C[q][v], calcul(v ^ (1 << q), vecs[q][i]) + matr[vecs[q][i]][q]);
			}
		}
		return C[q][v];
	}
	return C[q][v];
}

int main(int argc, char** argv) {

	ifstream fi("hamilton.in");
	ofstream fo("hamilton.out");

	int n, m, x, y, cost;
	fi >> n >> m;
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			matr[i][j] = MAXX;

	memset(C, -1, sizeof(C));
	vecs.resize(n);
	C[0][1] = 0;

	for (int i = 0; i < m; i ++) { 
		fi >> x >> y >> cost;
		matr[x][y] = cost;
		vecs[y].push_back(x);
	}

	int v = (1 << n) - 1;
	int sol = MAXX;

	for (unsigned int i = 0; i < vecs[0].size(); i++) {
		sol = min(sol, calcul(v, vecs[0][i]) + matr[vecs[0][i]][0]);
	}

	if (sol == MAXX)
		fo << "Nu exista solutie\n";
	else
		fo << sol << "\n";

	return 0;
}