#include <cstdio>
#include <vector>
#define N 100000000
using namespace std;
vector <int> v[20],c[20];

int ok[1004],n;

int rez(int k,int l)
{
	int sol=N,q;
	if (l==n+1) return 0;
	ok[k]=1;
	vector<int>::iterator it,it2;
	for (it=v[k].begin(),it2=c[k].begin();it!=v[k].end();++it,++it2)
		if (!ok[*it]) 
			{ q=rez(*it,l+1)+*it2;
				if (q<sol) sol=q;
			} else
				if ((*it==0) && (l==n))
					{ok[k]=0;return *it2;}
				
			
	ok[k]=0;
	return sol;
}	
			

int main()
{
	int i,a,b,cost,m;
	
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=m;i>0;--i)
	{ 
		scanf("%d %d %d",&a,&b,&cost);
		v[a].push_back(b);c[a].push_back(cost);}
	m=rez(0,1);
	if (m!=N)
	printf("%d",rez(0,1)); else
		printf("Nu exista solutie");
			
return 0;}