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

using namespace std;
int matr[18][18], C[18][262144];

int calcul(int ant, int v, int q, int n) {

	int maxi = numeric_limits<int>::max();
	if (C[q][v] == maxi) {
		if ((v ^ (1 << q)) !=  0) {
			for (int i = 0; i < n ; i++)
				if (i != q && matr[i][q] <  maxi && (v & (1 << i))) {
					int p =  calcul(q, v ^ (1 << q), i, n);
					if (p < maxi)
						C[q][v] = min(C[q][v], p + matr[i][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 imax = numeric_limits<int>::max();

	int n, m, x, y, cost;
	fi >> n;
	fi >> m;
	

	for (int i = 0; i < n; i++) { 
		for (int j = 0; j < (1<<n); j++) { 
			C[i][j] = imax;
		}
		for (int j = 0; j < n; j++) { 
			matr[i][j] = imax;
		}
	}

	C[0][1] = 0;

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

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

	for (int i = 0; i < n ; i++) {
		if (matr[i][0] < imax) {
			int p = calcul(0, v, i, n);
			if (p < imax)
				sol = min(sol, p + matr[i][0]);
		}
	}

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

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