using namespace std;
#include<fstream>
#include<vector>
#define MAX_N 20
#define oo 0x3f3f3f3f
int bst[262150][MAX_N];
int cost[MAX_N][MAX_N];
vector<int>G[MAX_N];
int N, M;
int main()
{
	ifstream f("hamilton.in"); ofstream g("hamilton.out");
	f>>N>>M;
	int i,j, v,cst,x,y; 
	unsigned k;
	for(i = 1; i <= M; ++i)
	{
		f>>x>>y>>cst;
		G[y].push_back(x);
		cost[x][y] = cst;
	}
	for(i = 0; i <= (1<<N); ++i)
		for(j = 0; j < N; ++j)
			bst[i][j] = oo;
	bst[1][0] = 0;
	for(i = 0; i < (1<<N); ++i)
		for(j = 0; j < N; ++j)
		{
			if(!(i & (1<<j))) continue;
			for(k = 0; k < G[j].size(); ++k)
						bst[i][j] = min(bst[i][j], bst[i ^ (1<<j)][ G[j][k] ] + cost[ G[j][k] ][j]);
		}
	int sol = oo;
	for (i = 0; i < G[0].size(); ++i)
        sol = min(sol, bst[(1<<N) - 1][ G[0][i] ] + cost[ G[0][i] ][0]);
	if(sol == oo) g<<"Nu exista solutie\n";
	else g<<sol<<"\n";
	return 0;
}