#include <fstream>
#include <vector>
#define oo (1<<30)
#define nmax 18
#define cmax 262145
using namespace std;

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

inline int _min(int a,int b){if(a<b) return a;return b;}

vector<int> V[nmax];
int Cost[nmax][nmax];
int C[cmax][nmax],CostT;
int M,N;

int main()
{
    int x,y,i,j;
    in>>N>>M;
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
            Cost[i][j]=oo;
    while(M--)
    {
        in>>x>>y;
        in>>Cost[x][y];
        V[y].push_back(x);//le pun invers
    }

   /* for(i=0;i<(1<<N);i++)
        for(j=0;j<N;j++)
            Cost[i][j]=oo;

    for(i=0;i<N;i++)
        Cost[1<<i][i]=0;//de la X la X am costul 0
    Cost[1][0] = 0;
    for(i=0;i<(1<<N);i++)
        for(y=0;y<N;y++)
            if(i&(1<<y))//daca i-ul are in binar si nodul y bifat
                for(j=0;j<V[y].size();j++)
                {
                    x = V[y][j];
                    if(i&(1<<x))//i-ul are in binar si nodul x bifat
                    {
                        Cost[i][y] = _min(Cost[i][y],Cost[i^(1<<y)][x]+C[x][y]);//i fara y + 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 (size_t k = 0; k < V[j].size(); ++k)
					if (i & (1<<V[j][k]))
						C[i][j] = min(C[i][j], C[i ^ (1<<j)][ V[j][k] ] + Cost[ V[j][k] ][j]);
    CostT=oo;
    //nu conteaza de unde inecepe ciclul asa ca va proni din 0
    /*for(i=0;i<V[0].size();i++)
    {
        y=V[0][i];
        CostT=_min(CostT,Cost[(1<<N)-1][y]+C[y][0]);
    }*/
    	for (size_t i = 0; i < V[0].size(); ++i)
		CostT = _min(CostT, C[(1<<N) - 1][ V[0][i] ] + Cost[ V[0][i] ][0]);

    if(CostT==oo)
        out<<"Nu exista solutie\n";
    else out<<CostT<<'\n';
    return 0;
}