#include <vector>
#include <cstdio>
#include <string>
#include <algorithm>
#include <string.h>
#define cat(c) while (c!='\n') fscanf(f,"%c",&c);
#define ct(c) while (c!='\n') scanf("%c",&c);
#define INF 100000000
using namespace std;
FILE *f,*g;
int a[20][20];
int d[(1<<18)+1][20];
int n,m,x,y,z,k,p,i,j;
vector <int> e[20];
int sol;

int main()
{
     f=fopen("hamilton.in","r");
     g=fopen("hamilton.out","w");

     fscanf(f,"%d%d",&n,&m);

     for (i=1;i<=m;i++)
     {
          fscanf(f,"%d%d%d",&x,&y,&z);
          a[x][y]=z;
          e[y].push_back(x);
     }

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

     p=(1<<n)-1;


     for (j=0;j<=p;j++)
          for (i=0;i<n;i++)
               d[j][i]=INF;
     d[1][0]=0;
     for (j=0;j<=p;j++)
          for (i=0;i<n;i++)
               if ((1<<i)&j)
                    for (k=0;k<e[i].size();k++)
                         if ( (1<<e[i][k])&j )
                              d[j][i]=min(d[j][i],d[(1<<i)xor j][e[i][k]]+a[e[i][k]][i]);


     sol=INF;
     for (i=0;i<e[0].size();i++)
          sol=min(sol,d[p][e[0][i]]+a[e[0][i]][0]);

     if (sol==INF)
          fprintf(g,"Nu exista solutie");
     else
          fprintf(g,"%d",sol);

	return 0;
}