#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <stack>
#define MAXN 18
using namespace std;

struct XYC{
  int x,y,c;
};

struct XC{
  int node,cost;
};

vector <XC> graf[MAXN];
int dina[MAXN][1<<MAXN];
int n,mi;

void AddEdge(XYC a){
  graf[a.x].push_back({a.y,a.c});
}

void DFS(int mask){
  int node,ans;
  for(node=0;node<n;node++){
    if(dina[node][mask]!=0){
      for(XC neigh : graf[node]){
        if((mask&(1<<neigh.node))==0){
          if(dina[node][mask]+neigh.cost<dina[neigh.node][mask+(1<<neigh.node)] || dina[neigh.node][mask+(1<<neigh.node)]==0){
            dina[neigh.node][mask+(1<<neigh.node)]=dina[node][mask]+neigh.cost;
          }
        }
        if(mask+(1<<neigh.node)==(1<<n)-1){
          for(XC last : graf[neigh.node]){
            if(last.node==0){
              ans=last.cost;
            }
          }
          if(mi>dina[node][mask]+neigh.cost+ans || mi==-1){
            mi=dina[node][mask]+neigh.cost+ans;
          }
        }
      }
    }
  }
}

int main(){
  int m,i;
  XYC a;
  FILE *fin,*fout;
  fin=fopen("hamilton.in","r");
  fout=fopen("hamilton.out","w");
  fscanf(fin,"%d%d",&n,&m);

  for(i=0;i<m;i++){
    fscanf(fin,"%d%d%d",&a.x,&a.y,&a.c);
    AddEdge(a);
  }

  dina[0][1]=1;

  mi=-1;
  for(i=1;i<(1<<n);i++){
    DFS(i);
  }

  if(mi==-1){
    fprintf(fout,"Nu exista solutie");
  }else{
    fprintf(fout,"%d",mi-1);
  }

  fclose(fin);
  fclose(fout);
  return 0;
}