#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 20;
const int MAXX = 262150;
const int INF = 100000000;

int Cost[MAXN][MAXN];
int C[MAXX][MAXN];
vector <int> A[MAXN];

int main()
{
	int n, m, sol;
	fstream fin("hamilton.in", fstream::in);
	fstream fout("hamilton.out", fstream::out);
	
	fin >> n >> m;
	
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			Cost[i][j] = INF;

	for (int i = 1; i <= m; ++i)
	{
		int x, y;

		fin >> x >> y;
		A[y].push_back(x);
		fin >> Cost[x][y];
	}

	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 = 0; i < (1 << n); ++i)
	{
		for (int j = 0; j < n; ++j)
			if (i & (1<<j))
			{
				for (size_t k = 0; k < A[j].size(); ++k)
					if (i & (1<<A[j][k]))
						C[i][j] = min(C[i][j], C[i ^ (1<<j)][ A[j][k] ] + Cost[ A[j][k] ][j]);
			}
	}

	sol = INF;
	for (size_t i = 0; i < A[0].size(); ++i)
		sol = min(sol, C[(1<<n) - 1][ A[0][i] ] + Cost[ A[0][i] ][0]);

	if (sol == INF)
		fout << "Nu exista solutie\n";
	else
		fout << sol << endl;
	
	fin.close();
	fout.close();
	return 0;
}