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

const int INFI = 20000000;
const int MAXN = 20;
const int MAXX = 262150;

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

int calcul(int v, int q) {

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

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] = INFI;

	memset(C, -1, sizeof(C));
	C[1][0] = 0;

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

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

	sol = INFI;

	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 == INFI)
		fo << "Nu exista solutie"<< endl;
	else
		fo << sol << endl;;

	return 0;
}