#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
struct nod{
    int inf;
    nod *urm;
}*L[20];
int cost[20][20],i,j,inf=100000000,c[500000][20],sol,n,m;
void adaugsf(nod *&vf,int val){
     nod *q;
     q=new nod;
     q->inf=val;
     q->urm=vf;
     vf=q;
}
void cit(){
    fin>>n>>m;
    int i,a,b,c;
    for (i=0;i<=n-1;i++)
        L[i]=0;
    for (i=1;i<=m;i++){
        fin>>a>>b>>c;
        adaugsf(L[b],a);
        cost[a][b]=c;
    }
    fin.close();
}
int calc(int putere,int nd){
    nod *q;
    int sw=0;
    if (c[putere][nd]==-1){
        c[putere][nd]=inf;
        q=L[nd];
        while(q!=0){
            if (putere & (1<<q->inf)){
                if (q->inf==0 && putere!=(1<<nd)+1) {
                    q=q->urm;
                    sw=1;
                }
                  else
                c[putere][nd]=min(c[putere][nd],calc(putere ^ (1<<nd),q->inf)+cost[q->inf][nd]);
            }
            if (sw==0) q=q->urm;
        }
    }
    return c[putere][nd];
}
int main(){
   for (i=0;i<n;i++)
    for (j=0;j<n;j++)
       cost[i][j]=inf;
   memset(c,-1,sizeof(c));
   cit();
   sol=inf;
   c[1][0]=0;
   nod *q;
   q=L[0];
   while(q!=0){
      sol=min(sol,calc((1<<n)-1,q->inf)+cost[q->inf][0]);
      q=q->urm;
   }
   if (sol==inf) fout<<"Nu exista solutie";
     else
        fout<<sol;
   fout.close();
   return 0;
}