#include<fstream>
#include<cstring>
#define inf (1<<30)
#define cm (1<<22)
#define N 22
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int a[N][N],C[cm][N],sol,conf,i,j,n,m,x,y;
int back(int x,int conf)
{
	if(C[conf][x]==-1)
	{
		C[conf][x]=inf;
		for(int i=1,p=1;i<=n;i++,p<<=1)
		{
			if((conf&p)&&a[i][x])
			{
				if(i==1&&conf!=(1<<(x-1)+1))
				continue;
				C[conf][x]=min(C[conf][x],back(conf-p,i)+a[i][x]);
			}
		}
	}
	return C[conf][x];
}
int main ()
{
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y;
		f>>a[x][y];
	}
	for(i=1;i<=n;++i)
	memset(C[i],-1,sizeof(C[i]));
	C[1][1]=0;
	sol=inf;
	conf=(1<<n)-1;
	for(i=2;i<=n;++i)
	if(a[i][1])
	sol=min(sol,back(i,conf)+a[i][1]);
	if(sol<inf)
	{
		g<<sol;
		return 0;
	}
	else
	g<<"Nu exista solutie";
	return 0;
}