#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 ant, int v, int q, int n) {

	if (C[q][v] == -1) {
		if ((v ^ (1 << q)) !=  0) {
			C[q][v] = MAXX;
			for (unsigned int i = 0; i <  vecs[q].size(); i++) {
				int ii = vecs[q][i];
				if (v & (1 << ii)) {
					C[q][v] = min(C[q][v], calcul(q, v ^ (1 << q), ii, n) + matr[ii][q]);
				}
			}
			return C[q][v];
		}
		return matr[0][q];
	}
	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 - 1;
	int sol = MAXX;

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

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

	fi.close();
	fo.close();
}