#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int MAX_N = 20;
const int INF = (1 << 30);
const int MAX_CONF = (1 << MAX_N);

int n, m, Cost[MAX_N][MAX_N], rez = INF;
int C[MAX_CONF][MAX_N];
vector <int> L[MAX_N];

void init() {
	for (int i = 0; i < MAX_N; i++)
		for (int j = 0; j < MAX_N; j++)
			Cost[i][j] = INF;
		
	for (int i = 0; i < MAX_CONF; i++)
		for (int j = 0; j < n; j++)
			C[i][j] = INF;
}

void read() {
	f >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		
		f >> a >> b >> c;
		L[b].push_back(a);
		Cost[a][b] = c;
	}
}

void solve() {
	C[1 << 0][0] = 0;		// lant care se termina in nodul 0 si contine doar nodul 0
	
	for (int conf = 0; conf < (1 << n); conf++)		// iau fiecare configuratie
		for (int j = 0; j < n; j++)		// iau fiecare nod
			if (conf & (1 << j)) {		// daca nodul j e in configuratie
				for (int k = 0; k < L[j].size(); k++) {
					int vecin = L[j][k];
					
					if (conf & (1 << vecin))		// daca nodul vecin e in configuratie
						C[conf][j] = min(C[conf][j], C[conf ^ (1 << j)][vecin] + Cost[vecin][j]);
				}
			}
}

void write() {
	int conf = (1 << n) - 1;
	
	for (int i = 0; i < L[0].size(); i++) {
		int vecin = L[0][i];
		
		// iau fiecare lant care incepe in 0 si se termina in vecin si contine toate nodurile
		// adaug muchia [vecin, 0] ca sa formeze ciclu
		rez = min(rez, C[conf][vecin] + Cost[vecin][0]);
	}
	
	if (rez == INF)
		g << "Nu exista solutie\n";
	else
		g << rez << '\n';
}

int main() {
	init();
	read();
	solve();
	write();
	
	f.close();
	g.close();
	
	return 0;
}