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

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

const int MAXN = 20;
const int MAXX = 1 << 18;
const int INF = 0x3f3f3f3f;

int n, m, Sol;
vector <int> A[MAXN];
int dp[MAXX][MAXN];
int Cost[MAXN][MAXN];

int calc(int conf, int last)
{
	if (dp[conf][last] == -1)
	{
		dp[conf][last] = INF;

		for (int i = 0; i < A[last].size(); i++)
			if (conf & (1 << A[last][i]))
			{
				if (A[last][i] == 0 && conf != (1 << (last)) + 1)
					continue;

				dp[conf][last] = min(dp[conf][last], calc(conf ^ (1 << last), A[last][i]) + Cost[A[last][i]][last]);
			}
	}

	return dp[conf][last];
}

int main()
{
	Sol = INF;

	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];
	}

	memset(dp, -1, sizeof(dp));
	dp[1][0] = 0;

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

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

	return 0;
}