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