#include<fstream>
#include<cstring>
using namespace std;
typedef struct celula {
           int nod,cost;
           celula *next;
           } *lista;
lista graf[20],v;
int i,j,n,m,x,y,c,sol[263000][20],inf=1000000007;

int main(void) {
     ifstream fin("hamilton.in");
     ofstream fout("hamilton.out");
     fin>>n>>m;
     for (i=1; i<=m; ++i) {
         fin>>x>>y>>c;
         v=new celula; v->nod=x; v->cost=c; v->next=graf[y]; graf[y]=v;
         }
     //initializarea
     int k=(1<<n)-1;
     for (i=0; i<=k; ++i)
      for (j=0; j<n; ++j) sol[i][j]=inf;
     sol[1][0]=0;
     
     //dinamica sol[i][j]=costul minim pentru un lant car incepe in 0 se termina in j si trece prin nodurile din config binara a lui i
     for (i=2; i<=k; ++i)
      for (j=0; j<n; ++j)
       if ( i&(1<<j) > 0 ) {//daca nodul j se afla in configuratia lui j atunci incerc sa-l leg pe j de un alt nod din configuratie
       
          for (lista p=graf[j]; p; p=p->next)
           if ( i&(1<<p->nod) > 0 ) sol[i][j]=min(sol[i][j],sol[i^(1<<j)][p->nod]+p->cost);
       }
     //caut solutia verificind punctele finale
     int rez=inf;
      
     for (lista p=graf[0]; p; p=p->next)
        rez=min(rez,sol[k][p->nod]+p->cost);
         
    if (rez==inf) fout<<"Nu exista solutie";
     else fout<<rez;
    
    return 0;
}