#include <cstdio>
using namespace std;
#define nmax 18
FILE *f=fopen("hamilton.in","r");
FILE *g=fopen("hamilton.out","w");
int n,m;
bool viz[nmax];
int ndr,cost,c;
struct graf
 {
 int x;
 graf *urm;
 };
graf *G[nmax];
int C[nmax][nmax];
void add(graf *&g,int x)
 {
 graf *p=new graf;
 p->x=x;
 p->urm=g;
 g=p;
 }
void read()
 {
 fscanf(f,"%d %d",&n,&m);
 int i,x,y,c;
 for(i=1;i<=m;i++)
  {
  fscanf(f,"%d %d %d",&x,&y,&c);
  add(G[x],y);
  C[x][y]=c;
  }
 }
void back(int nod)
 {
 ++ndr;
 viz[nod]=true;
 for(graf *g=G[nod];g!=NULL;g=g->urm)
  {
  if(ndr==n&&g->x==0)
   {
   c+=C[nod][g->x];
   if(cost==0||cost>c)
	cost=c;
   }
  else
   {
   
    if(!viz[g->x])
	 {
	 c+=C[nod][g->x];
	 back(g->x);
	 c-=C[nod][g->x];
	 }
   }
  }
 --ndr;
 viz[nod]=false;
 }
int main()
 {
 read();
 back(0);
 if(cost==0)
  fprintf(g,"Nu exista solutie");
 else
  fprintf(g,"%d",cost);
 return 0;
 }