#include<fstream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;


ifstream in("hamilton.in");
ofstream out("hamilton.out");

int G[20][20];

int D[20][1 << 20];

int N,M;

int main()
{
	in >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int x, y, c;
		in >> x >> y >> c;
		if (y != 0)
			G[x][y] = c;
		else
			G[x][19] = c;
	}
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < (1 << N); ++j)
			D[i][j] = (1 << 30);
	for (int i = 0; i < N; ++i)
		D[i][1 << i] = 0;
	for (int j = 1; j < (1 << N); ++j)
	{
		for (int k = 0; k < N; ++k)
		  if(j&(1<<k))
			for (int i = 0; i < N; ++i)
			{
					if (G[i][k] != 0 && i!=k &&(j&(1<<i)))
						D[k][j] = min(D[k][j], D[i][j ^ (1 << k)] + G[i][k]);
			}
	}

	int mn = (1 << 30);

	for (int i = 0; i < N; ++i)
		if(G[i][19])
			mn = min(mn, D[i][(1 << N) - 1]+G[i][19]);
	if (mn == (1<<30))
		out << "Nu exista solutie";
	else
		out << mn;

	return 0;
}