#include<fstream>
using namespace std;
struct nod{int info,c;nod *adr;}*v[20],*p;
int ch[100],n,m,i,x,y,j,c,a[20][20],k;
long long minn=99999999999999999ll;
ofstream g("hamilton.out");
int valid(int k)
{
   //daca (k==n) => nodul ch[k] sa fie legat de nodul initial (1)
	if(k==n)
	{
	 nod *p = v[ch[k]];
	 while(p && p->info!=0) p=p->adr;
	  if(!p) return 0;
	}
   //nodul care il introduc sa nu mai fie in ciclu
	for(j=1;j<k;j++)   if(ch[j]==ch[k]) return 0;
 return 1;
}
long long cost()
{long long rez=0;
	for(int i=2;i<=n+1;i++) rez+=(a[ch[i-1]][ch[i]]);
		return rez;
}
void back(int k)
{
	if(k==n+1) 
	{
		int mn=cost();
		if(mn<minn)minn=mn;
	}
	else//parcurg vecinii nodului
	{
	  nod *p=v[ch[k-1]];
	  while(p)
	  {
		 ch[k]=p->info;
		 if(valid(k)) 
			 back(k+1); 
		 p=p->adr;
	  }
	}
}
int main()
{
	ifstream f("hamilton.in");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		a[x][y]=c;
		p=new nod;
		p->info=y; p->adr=v[x]; p->c=c; v[x]=p;
	}
	for(i=0;i<n;i++)
	{
		k=0;
		for(j=0;j<n;j++) if(a[i][j]){k=1; break;}
		if(!k){ g<<"Nu exista solutie"; return 0;}
	}
	for(i=0;i<n;i++)
	{
		k=0;
		for(j=0;j<n;j++) if(a[j][i]){k=1; break;}
		if(!k){ g<<"Nu exista solutie"; return 0;}
	}
	ch[1]=0;
	back(2);
	if(minn==99999999999999999ll)g<<"Nu exista solutie";else 
	g<<minn;
	f.close();g.close();
return 0;}