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

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

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

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


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