#include <fstream>
#include <vector>
#define INF 20000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

vector <int> mc[18];

int c[18][18],sol[1<<18][18];

inline int mi(int x,int y) {return ((x<y)? x:y);}

int rez(int secv,int l)
{
	if (!sol[secv][l]) 
	{
	sol[secv][l]=INF;
	for (size_t i=0;i<mc[l].size();++i)
		if (secv&(1<<mc[l][i]))
		{
			if ((mc[l][i]==0) && (secv!=(1<<0)))
				continue;
			sol[secv][l]=mi(sol[secv][l],rez(secv^(1<<mc[l][i]),mc[l][i])+c[mc[l][i]][l]);
		}
	}
	return sol[secv][l];	
}		


int main()
{
	int n,m,w=INF;
	f>>n>>m;
	while (m--)
	{ 
		int i,j;
		f>>i>>j;
		f>>c[i][j];
		mc[j].push_back(i);
	}
	sol[0][0]=1;
	for (size_t x=0;x<mc[0].size();++x)
		w=mi(w,rez(((1<<n)-1)^(1<<mc[0][x]),mc[0][x])+c[mc[0][x]][0]);
	if (w!=INF)
	g<<w-1; else g<<"Nu exista solutie";
	f.close();
	g.close();
	
return 0;}