#include<stdio.h>
#include<vector>
using namespace std;

FILE *f = fopen("hamilton.in","r");
FILE *g = fopen("hamilton.out","w");

typedef vector<int>::iterator it;

#define MaxN 19
#define Max2maxN ((1<<18)+100)
#define INF (1<<29)
#define sh short int

int N,M;
int Best[MaxN][Max2maxN];
int Cost[MaxN][MaxN];
vector<int> A[MaxN];
int Sol = INF;

void citire(void)
{
    int a,b,c;

    fscanf(f,"%d %d\n",&N,&M);
    for(int i=1;i<=M;i++)
    {
        fscanf(f,"%d %d %d",&a,&b,&c);
        A[a].push_back(b);
        Cost[a][b] = c;
    }
}

void Initializare(void)
{
    for(int i=0;i<N;i++)
        for(int j=(1<<N)-1;j;j--)
            Best[i][j] = INF;

    Best[0][1] = 0;
}

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

void Rezolvare(void)
{
    Initializare();

    for(int i=2;i<N;i++)
        for(int j=0;j<N;j++)
           for(int k=(1<<N)-1;k;k--)
              if(Best[j][k] != INF)
                for(it l=A[j].begin();l<A[j].end();l++)
                   if(! ((1<<(*l)) & k)) 
                      Best[*l][(1<<(*l))^k] = min(Best[*l][(1<<(*l))^k],Best[j][k] + Cost[j][*l]); 

    //for(int i=0;i<N;i++,printf("\n\nS-a terminat\n\n"))
    //    for(int j=0;j<(1<<N);j++)
    //        printf("%d %d -> %d\n",i,j,Best[i][j]);

    for(int i=1;i<N;i++)
        if(Cost[i][0] > 0)
            Sol = min(Sol, Best[i][ (1<<N)-1 ]+Cost[i][0]);
}

int main()
{
    citire();
    Rezolvare();

    fprintf(g,(Sol == INF) ? "Nu exista solutie\n" : "%d\n",Sol);
}