#include <fstream>
#include <vector>
#include <cstring>

const int MAXX = 20000000;

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

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])) {
				if (vecs[q][i] == 0 && v != (1<<(q)) + 1) continue;
				C[q][v] = min(C[q][v], calcul(v ^ (1 << q), vecs[q][i]) + matr[vecs[q][i]][q]);
			}
		}
	}
	return C[q][v];
}

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

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

	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));
	C[0][1] = 0;

	for (int i = 0; i < m; i ++) { 
		int x, y;

		fi >> x >> y;
		vecs[y].push_back(x);
		fi >> matr[x][y];
	}

	sol = MAXX;

	for (size_t i = 0; i < vecs[0].size(); i++) {
		sol = min(sol, calcul((1 << n) - 1, vecs[0][i]) + matr[vecs[0][i]][0]);
	}

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

	return 0;
}