#include <fstream>
#include <limits>
#define NMax 20
using namespace std;

int N, M, A;
int COST[NMax][NMax];
int CMIN[1 << NMax][NMax];
const int INF = numeric_limits<int>::max();

void read()
{
	int x, y, c;
	ifstream fin("hamilton.in");
	fin >> N >> M;
	for (x = 0; x < N; ++x)
		for (y = 0; y < N; ++y)
			COST[x][y] = INF;
	while (M--)
	{
		fin >> x >> y >> c;
		COST[x][y] = c;
	}
}

void solve()
{
	int j, k, v;
	CMIN[1][0] = 0;
	for (j = 2; j < (1 << N); ++j)
		for (k = 0; k < N; ++k)
			if (j != 1 || k != 0)
			{
				CMIN[j][k] = INF;
				if (j & (1 << k))
					for (v = 0; v < N; ++v)
						if (j & (1 << v) 
								&& COST[v][k] < INF 
								&& CMIN[j ^ (1 << k)][v] < INF 
								&& CMIN[j][k] > CMIN[j ^ (1 << k)][v] + COST[v][k])
							CMIN[j][k] = CMIN[j ^ (1 << k)][v] + COST[v][k];
			}
	A = INF;
	for (k = 0; k < N; ++k)
		if (COST[k][0] < INF 
				&& CMIN[(1 << N) - 1][k] < INF 
				&& CMIN[(1 << N) - 1][k] + COST[k][0] < A)
			A = CMIN[(1 << N) - 1][k] + COST[k][0];
}

void write()
{
	ofstream fout("hamilton.out");
	if (A < INF)
		fout << A << '\n';
	else
		fout << "Nu exista solutie\n";
	fout.close();
}

int main()
{
	read();
	solve();
	write();
	return 0;
}