#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9;
#define NMAX 20

int n, m;

int cost[NMAX][NMAX];
int dp[1 << (NMAX - 1)][NMAX];
vector<int> adj[NMAX];

int main()
{
	/*freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);*/
	ifstream fin("hamilton.in");
	ofstream fout("hamilton.out");
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		fin >> x >> y;
		adj[y].push_back(x);
		fin >> cost[x][y];
	}
	for (int i = 0; i < (1 << n); i++)
		for (int j = 0; j < n; j++)
			dp[i][j] = INF;
	dp[1][0] = 0;
	for (int i = 0; i < (1 << n); i++)
		for (int j = 0; j < n; j++) {
			if (i & (1 << j))
				for (auto it : adj[j])
					if (i && (1 << it))
						dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][it] + cost[it][j]);
		}
	int sol = INF;
	for (auto it : adj[0])
		sol = min(sol, dp[(1 << n) - 1][it] + cost[it][0]);
	if (sol != INF)
		fout << sol << '\n';
	else
		fout << "Nu exista solutie\n";
	fin.close();
	fout.close();
	return 0;
}