#include<fstream.h>
#include<iostream.h>
#define u 1<<30
int a[20][20],c[19][1<<18],ver[1000],start[20],leg[1000];
int calc(int j, int nod)
{
	int t=start[nod],temp;
	if(c[nod][j]==-1)
		c[nod][j]=u;
	while(t)
	{
		if(j&(1<<ver[t]))
			if(ver[t]||j==(1<<nod)+1)
			{
				temp=calc(j^(1<<nod),ver[t])+a[ver[t]][nod];
				if(c[nod][j]>temp)
					c[nod][j]=temp;
			}
		t=leg[t];
	}
	return c[nod][j];
}
int main()
{
	int n,m,t,sol,i,j,x,y,q=0,temp;
	ifstream f("hamilton.in");
	ofstream g("hamilton.out");
	f>>n>>m;
	sol=u;
	memset(a,u,sizeof(a));
	memset(c,-1,sizeof(c));
	while(m--)
	{
		f>>x>>y;
		f>>a[x][y];
		ver[++q]=x;
		leg[q]=start[y];
		start[y]=q;
	}
	c[0][1]=0;
	t=start[0];
	while(t)
	{
		temp=calc((1<<n)-1,ver[t])+a[ver[t]][0];
		if(sol>temp)
			sol=temp;
		t=leg[t];
	}
	if(sol==u)
		g<<"Nu exista solutie";
	else
		g<<sol;
	return 0;
}