#include<fstream.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]==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;
	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<(1<<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<(1<<n);j++)
		for(i=0;i<n;i++)
			if(j&(1<<i))
			{
				t=start[i];
				while(t)
				{
					if(j&(1<<ver[t]))
						if(c[ver[t]][j^(1<<i)]+a[ver[t]][i]<c[i][j])
							c[i][j]=c[ver[t]][j^(1<<i)]+a[ver[t]][i];
					t=leg[t];
				}
			}
	t=start[0];
	while(t)
	{
		if(sol>c[ver[t]][(1<<n)-1]+a[ver[t]][0])
			sol=c[ver[t]][(1<<n)-1]+a[ver[t]][0];
		t=leg[t];
	}
	if(sol==u)
		g<<"Nu exista solutie";
	else
		g<<sol;
	return 0;
}