#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define N 18
#define fs first
#define sc second
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
int n;
const int inf=1000000000;
int d[1<<N][N];
vector< pii > a[N]; 
inline void citire()
{
	int m,x,y,z;
	scanf("%d%d",&n,&m);
        for(int i=0; i<m; ++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[y].pb(mp(x,z));//inversat
	}
}
inline int minim(int x,int y)
{
	if(x<y)
		return x;
	return y;
}
inline void rezolva()
{
	int lim=1<<n;
	int aux;
	d[1][0]=0;
	for(int i=1; i<lim; ++i)
	{
		for(int j=0; j<n; ++j)
		{
			if(i!=1 || j!=0)
				d[i][j]=inf;
			if(i&(1<<j))
			{
				aux=i^(1<<j);
            			for(size_t w=0,lim1=a[j].size(); w<lim1; ++w)
				{
					if(i&(1<<a[j][w].fs))
                                		d[i][j]=minim(d[i][j],d[aux][a[j][w].fs]+a[j][w].sc);
				}
			}
		}
	}
}
inline void scrie()
{
	int rez=inf;
	int n1=(1<<n)-1;
	for(size_t i=0,lim=a[0].size(); i<lim; ++i)
		rez=minim(rez,d[n1][a[0][i].fs]+a[0][i].sc);

	if(rez==inf)
	{
		fputs("Nu exista solutie\n",stdout);
		return;
	}
	printf("%d\n",rez);
}
int main()
{
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);

	citire();
        rezolva();
	scrie();

	return 0;
}