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


typedef std::vector< int >::iterator iter;


const int MAXN = 18;
const int INF = 0x3f3f3f3f;
std::ifstream f("hamilton.in");
std::ofstream g("hamilton.out");
int n, m;
std::vector< int > G[MAXN];
int dist[MAXN][MAXN];
int dp[1 << MAXN][MAXN];


int main()
{
	memset(dist, 0x3f, sizeof(dist));
	memset(dp, 0x3f, sizeof(dp));

	f >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		f >> x >> y >> c;
		G[y].push_back(x);
		dist[x][y] = c;
	}

	for (int i = 0; i < n; i++) {
		dp[1 << i][i] = 0;
	}
	for (int mask = 1; mask < (1 << n); mask++) {
		for (int x = 0; x < n; x++) {
			if ((mask & (1 << x)) == 0) {
				continue;
			}

			for (iter it = G[x].begin(); it != G[x].end(); it++) {
				int y = *it;
				if ((mask & (1 << y)) == 0) {
					continue;
				}

				dp[mask][x] = std::min(dp[mask][x], dp[mask ^ (1 << x)][y] + dist[y][x]);
			}
		}
	}

	int mn = INF;
	for (iter it = G[0].begin(); it != G[0].end(); it++) {
		int y = *it;
		mn = std::min(mn, dp[(1 << n) - 1][y] + dist[y][0]);
	}
	if (mn == INF) {
		g << "Nu exista solutie" << std::endl;
	}
	else {
		g << mn << std::endl;
	}


	f.close();
	g.close();
	return 0;
}