#include <stdio.h>
#include <vector>
#define IN "hamilton.in"
#define OUT "hamilton.out"
#define Lg 270000
#define oo 100000000

using namespace std;

int N, M, Sol;
int x, y;
int Cost[20][20];
int C[Lg][20];
vector<int> A[20];

int main()
{
    freopen (IN ,"r", stdin);
    freopen (OUT ,"w", stdout);

    scanf ("%d %d",&N,&M);

	for (int i=0;i<N;++i)
		for (int j=0;j<N;++j)
            Cost[i][j]=oo;

	for (int i=1;i<=M;++i)
	{
		scanf ("%d %d",&x, &y);
		A[y].push_back(x);
		scanf ("%d",&Cost[x][y]);
	}
	for (int i=0;i<1<<N;++i)
		for (int j=0;j<N;++j) C[i][j]=oo;
	C[1][0]=0;

	for (int i=0;i<1<<N;++i)
		for (int j=0;j<N;++j)
			if (i& (1<<j))
				for (int k=0;k<A[j].size();++k)
					if (i& (1<<A[j][k]))
						C[i][j]=min(C[i][j], C[i^ (1<<j)][A[j][k]] + Cost[A[j][k]][j]);
	Sol=oo;
	for (int i=0;i<A[0].size();++i)
		Sol=min(Sol, C[(1<<N)-1][A[0][i]]+Cost[A[0][i]][0]);

	if (Sol==oo)
        printf("Nu exista solutie\n");
	else
        printf("%d\n",Sol);
	return 0;
}