#include<iostream>
#include<fstream>
using namespace std;
#define bit( x , nr ) (  ( (x) & ( 1 << (nr) ) ) != 0)
const int NMAX = 19;
const int INF = 1<<30;
int a[NMAX][NMAX],v[NMAX],d[NMAX][1<<NMAX],n;
int calc(int i, int s)
{
	int j;
	if((1<<i)==s)
		d[i][s]=0;
	else if(d[i][s]==INF) {
		for(j=0;j<=n-1;j++)
			if( bit(s,j) && i!=j && a[j][i] )
				d[i][s]=min(d[i][s],calc(j,s-(1<<i))+a[j][i]);
	}
	return d[i][s];
}
int main ()
{
	int i,j,m,x,y,costmin;
	ifstream f("hamilton.in");
	ofstream g("hamilton.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y;
		f>>a[x][y];
		if(y==0)
			v[++v[0]]=x;
	}
	f.close();
	for(i=0;i<=n;i++)
		for(j=0;j<=(1<<n);j++)
			d[i][j]=INF;
	costmin=INF;
	for(i=1;i<=v[0];i++) {
		x=a[0][v[i]];
		a[0][v[i]]=0;
		costmin=min(costmin,calc(v[i],(1<<n)-1)+a[v[i]][0]);
		a[0][v[i]]=x;
	}
	if(costmin==INF)
		g<<"Nu exista solutie\n";
	else g<<costmin;
	g.close();
	return 0;
}