#include<cstdio>
#include<algorithm>
#include<vector>

const int NMAX=19,INF=2047483647;

std::vector<std::pair<int,int> > vecini[NMAX];

///d[i][mask] = costul minim al unui ciclu care incepe la 1 si se termina la i si contine nodurile mask
int d[NMAX][1<<NMAX];

int main()
{
 FILE *in=fopen("hamilton.in","r");
 int n,m;
 fscanf(in,"%d %d ",&n,&m);
 for(int i=1;i<=m;i++)
     {
      int x,y,cost;
      fscanf(in,"%d %d %d ",&x,&y,&cost);
      vecini[y].push_back(std::make_pair(x,cost));
     }
 fclose(in);
 for(int i=0;i<n;i++)
     for(int j=0;j<(1<<n);j++)
         d[i][j]=INF;
 d[0][1]=0;
 for(int mask=0;mask<(1<<n);mask++)
     {
      for(int i=0;i<n;i++)
          {
           if(!(mask & (1<<i)))
              continue;
           for(int j=0;j<vecini[i].size();j++)
               {
                int k=vecini[i][j].first;
                if(!(mask & (1<<k)))
                   continue;
                d[i][mask]=std::min(d[i][mask],d[k][mask-(1<<i)]+vecini[i][j].second);
               }
          }
     }
 int rasp=INF;
 for(int i=0;i<vecini[0].size();i++)
     rasp=std::min(rasp,d[vecini[0][i].first][(1<<n)-1]+vecini[0][i].second);
 FILE *out=fopen("hamilton.out","w");
 if(rasp==INF)
    fprintf(out,"Nu exista solutie");
 else
    fprintf(out,"%d\n",rasp);
 fclose(out);
 return 0;
}