#include <fstream>
#include <vector>
using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");

const int N=20;
const int inf=0x3f3f3f3f;

struct nod
{
	int varf,cost;
};

vector <nod> a[N];

int d[(1<<N)][N];
int v[N];
int n,m;
int pred[N];



inline int min(int a,int b)
{
	return a<b ? a:b;
}


void hamilton()
{
	int i,j;

    for(i=1;i<=1<<n;i++)
        for(j=0;j<=n;j++)
            d[i][j]=inf;
    d[1][0]=0;

	for(i=2;i<=(1<<n);i++)
		for(j=0;j<n;j++)
		{
			if(i&(1<<j))
			{
				for(vector<nod> :: iterator k=a[j].begin(); k!=a[j].end();k++)
					if(i&(1<<((*k).varf)))
                        d[i][j]=min(d[i][j],d[i^(1<<j)][(*k).varf]+(*k).cost);
			}

        }
}

int main()
{
	int minim=inf,i,j,x,y,c,k=0;
	in>>n>>m;

	for(i=1;i<=n;i++)
		v[i]=inf;

	for(i=1;i<=m;i++)
	{
		in>>x>>y>>c;
		a[y].push_back((nod) {x,c});
		if(y==0)
		{
			v[++k]=c;
			pred[k]=x;
		}

	}

	hamilton();


    for(i=1;i<=k;i++)
	{
		if(d[(1<<n)-1][i]+v[i]<minim)
			minim=d[(1<<n)-1][pred[i]]+v[i];
	}

	if(minim!=inf)
		out<<minim;
	else
		out<<"Nu exista solutie";

	return 0;
}