#include <fstream>
#include <vector>
#define oo (1<<30)
#define nmax 19
#include <windows.h>
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[1<<nmax][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;

    for(i=0;i<N;i++)
        Cost[1<<i][i]=0;//de la X la X am costul 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
                    }
                }
    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]);
    }
    if(CostT==oo)
        out<<"Nu exista solutie\n";
    else out<<CostT<<'\n';
    return 0;
}