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

using namespace std;

const int INF = 0x3f3f3f3f;

int N, M;
vector<int> V[18];
int C[1 << 18][18], cost[18][18];
int result = INF;

int main()
{
	ifstream fin("hamilton.in");
	ofstream fout("hamilton.out");
	
	memset(cost, -1, sizeof(cost));
	
	fin >> N >> M;
	for (int i = 1, nod1, nod2; i <= M; ++i)
	{
		fin >> nod1 >> nod2;
		fin >> cost[nod1][nod2];
		V[nod2].push_back(nod1);
	}
	for (int i = 0; i < (1 << N); ++i)
		for (int j = 0; j < N; ++j)
			C[i][j] = INF;
	C[1][0] = 0;
	
	for (int i = 1; i < (1 << N); ++i)
		for (int j = 0; j < N; ++j)
			if (i & (1 << j))
				for (vector<int>::iterator k = V[j].begin(); k != V[j].end(); ++k)
					if (i & (1 << *k))
						C[i][j] = min(C[i][j], C[i ^ (1 << j)][*k] + cost[*k][j]);
	
	for (int i = 0; i < N; ++i)
		if (C[(1 << N) - 1][i] != INF && cost[i][0] != -1)
			result = min(result, C[(1 << N) - 1][i] + cost[i][0]);
	
	if (N == 1) result = 0;
	
	if (result == INF)
		fout << "Nu exista solutie\n";
	else
		fout << result << '\n';
	
	fin.close();
	fout.close();
}