#include<fstream>
#include<vector>
#define u 1<<30
using namespace std;
int a[20][20],c[19][1<<18];
vector <int> b[20];
int calc(int j, int nod)
{
	int temp;
	if(c[nod][j]==u)
	{
		for(size_t i=0;i<b[nod].size();i++)
		{
			if(j&(1<<b[nod][i]))
				if(b[nod][i]||j==(1<<nod)+1)
				{
					temp=calc(j^(1<<nod),b[nod][i])+a[b[nod][i]][nod];
					if(c[nod][j]>temp)
						c[nod][j]=temp;
				}
		}
	}		
	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];
		b[y].push_back(x);
	}
	c[0][1]=0;
	for(size_t i=0;i<b[0].size();i++)
	{
		temp=calc((1<<n)-1,b[0][i])+a[b[0][i]][0];
		if(sol>temp)
			sol=temp;
	}
	if(sol==u)
		g<<"Nu exista solutie";
	else
		g<<sol;
	return 0;
}