#include <fstream>
#include <vector>

using namespace std;

#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)

const int MAX_N = 20;
const int MAX_S = (1 << 18);
const int INF = 0x3f3f3f3f;

ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");

int N, M, K, C[MAX_S][MAX_N], D[MAX_N][MAX_N];
vector <int> G[MAX_N];

void citire()
{
	fin >> N >> M;

	for(int i = 1; i <= M; ++i)
	{
		int a, b, c;
		fin >> a >> b >> c;

		D[a][b] = c;
		G[b].push_back(a);
	}
}

void solve()
{
	memset(C, INF, sizeof C);
	C[1][0] = 0;

	K = (1 << N);
	for(int i = 1; i < K; ++i)
		for(int j = 0; j < N; ++j)
			if(i & (1 << j))
				foreach(G[j])
					if(i & (1 << *it))
						C[i][j] = min(C[i][j], C[i ^ (1 << j)][*it] + D[*it][j]);

	int Sol = INF;
	foreach(G[0])
		Sol = min(Sol, C[K - 1][*it] + D[*it][0]);
	

	if(Sol == INF)
		fout << "Nu exista solutie\n";
	else
		fout << Sol << "\n";
}

int main()
{
	citire();
	solve();
}