#include <stdio.h>
#include <vector>
#define INF 1<<30

std::vector<int> a[18];
int cost[19][19];


int d[(1<<18)+1][18];

int main(){

   freopen("hamilton.in","r",stdin);
   freopen("hamilton.out","w",stdout);

   int n,m;
   scanf("%d %d\n",&n,&m);

   for (int i=1;i<=m;i++){
      int x,y,z;
      scanf("%d %d %d",&x,&y,&z);

      a[y].push_back(x);
      cost[x][y]=z;

   }


   for (int i=0;i<(1<<n);i++)for (int j=0;j<n;j++)d[i][j]=INF;

   d[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++){
               int p=a[j][k];
               //exista p in i         costul care se termina in p care nu-l contine pe j  + costul de la p la j < d[i][j]
               if (( i&(1<<p)) && (d[i^(1<<j)][p] + cost[p][j] < d[i][j])){
                  d[i][j]=d[i^(1<<j)][p]+cost[p][j];
               }
            }
         }

      }

   }
   int sol=INF;

   for (int i=0;i<a[0].size();i++){
      int t=a[0][i];
      sol=std::min(sol,d[(1<<n)-1][ t ]+cost[ t ][0]);
   }
   if (sol==INF){
      printf("Nu exista solutie");
   } else{
      printf("%d",sol);
   }
   return 0;

}