#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 C[nmax][nmax];
int Cost[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++)
            C[i][j]=oo;
    while(M--)
    {
        in>>x>>y;
        in>>C[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;

    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)
			if (i & (1<<j))
				for (size_t k = 0; k < V[j].size(); ++k)
					if (i & (1<<V[j][k]))
						Cost[i][j] = min(Cost[i][j], Cost[i ^ (1<<j)][ V[j][k] ] + C[ 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, Cost[(1<<N) - 1][ V[0][i] ] + C[ V[0][i] ][0]);

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