#include<fstream>
#include<cstdio>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;++a)
#include<cstring>
#include<bitset>
#include<cmath>
#include<iomanip>
#include<queue>
#define f cin
#define g cout
#define mp make_pair
#define pb push_back
#define ll long long
#define inf 0x3f3f3f3f
#define base 256
#define bit 270000
#define N 19
#define M 50100
#define EPS 1e-12
#define mod  98999
#define inu "hamilton.in"
#define outu "hamilton.out"
using namespace std;
ifstream f(inu);
ofstream g(outu);
//int dx[]={0,0,0,1,-1};
//int dy[]={0,1,-1,0,0};
vector<pair<int,int> > v[N];
int best,lim,x,y,c,n,m,D[N][bit];
int main ()
{
	f>>n>>m;
	FOR(i,1,m)
	{
		f>>x>>y>>c;
		x++; y++; v[y].pb(mp(x,c));
	}
	lim=(1<<n);
	memset(D,inf,sizeof(D));
	D[1][1]=0;
	lim--;
	FOR(i,1,lim)
	for(int p=1,j=1;j<=n;p<<=1,j++)
	{
		if(i&p)
		{
			for(int k=0;k<v[j].size();++k)
			{
				int des=v[j][k].first;
				int cos=v[j][k].second;
				if((1<<(des-1))&i)
					D[j][i]=min(D[j][i],D[des][i-p]+cos);
			}
		}
	}
	best=inf;
	for(int i=0;i<v[1].size();++i)
	{
		int des=v[1][i].first;
		int cos=v[1][i].second;
		if(D[des][lim]+cos<best)
			best=D[des][lim]+cos;
	}
	if(best!=inf)
	g<<best;
	else
		g<<"Nu exista solutie";
    return 0;
}