#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define dbg(i) (cout<<#i<<" = "<<(i)<<'\n')

using ll = long long;
using ui = unsigned int;


const string fn = "hamilton";

ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

const int inf = 2e9;

int xMax;

int n, m;
int g[20][20];
int dp[20][(1 << 18) + 2];

/**
 * dp[i][x] = cost minim drum de la
 * 0 la i trecand prin nodurile marcate cu 1
 * in binarul lui x
 *
*/


int main() {

	int x, y, w;

	fin >> n >> m;

	for (int i = 1; i <= m; ++i) {
		fin >> x >> y >> w;
		g[x][y] = w;
	}

	xMax = (1 << n);

	for (int i = 0; i < n; ++i)
		for (int j = 1; j < xMax; ++j)
			dp[i][j] = inf;

	dp[0][1] = 0;
	///radacinat in 1
	for (int x = 3; x < xMax; x += 2) {
		for (int i = 1; i < n; ++i)
			if (x & (1 << i)) { // daca imi cuprinde nodul curent
				/// fara i
				int nou = x ^ (1 << i);
				for (int j = 0; j < n; ++j)
					if ((nou & (1 << j)) && g[j][i] > 0)
						dp[i][x] = min(dp[i][x], dp[j][nou] + g[j][i]);
			}
	}

	int ans = inf;
	for (int i = 1; i < n; ++i)
		if (dp[i][xMax - 1] != inf && g[i][0])///pot completa
			ans = min(ans, dp[i][xMax - 1] + g[i][0]);

	if (ans == inf) fout << "Nu exista solutie\n";
	else fout << ans << '\n';

	fin.close();
	fout.close();
	return 0;
}