#include <stdio.h>
#include <string.h>
#define NMAX 18
#define Inf 0x3f3f3f3f
int N,M,Cost[NMAX][NMAX],Din[NMAX][1<<NMAX];
/*
   fixam nodul 0 ca ult nod al ciclului
   si calculam Din[i][k]=costul min al unui lant ce incepe in i (si se termina in 0)
   si trece prin nodurile din repr bin al lui k
*/
inline int min(int x,int y) {return x<y?x:y;}
int  Calc(int x,int k)
{
     if (k==(1<<x)) return 0;
     if (k==(1<<x)+1 && Cost[x][0]>0) Din[x][k]=Cost[x][0];
     if (Din[x][k]==-1)
     {
      int i,ret=Inf;
      for (i=1;i<N;++i)
           if (Cost[x][i]>0 && (1<<i)&k)
             ret=min(ret,Cost[x][i]+Calc(i,k-(1<<x)));
      Din[x][k]=ret;
     }
     return Din[x][k];
}
int main()
{
    int i,j,k;
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d %d",&N,&M);
    while (M--)
    {
          scanf("%d %d %d",&i,&j,&k);
          Cost[i][j]=k;
    }
   
    memset(Din,-1,sizeof(Din));
    int Sol=Inf;
    for (i=1;i<N;++i)
      if (Cost[0][i]>0)
        Sol=min(Sol,Calc(i,(1<<N)-1)+Cost[0][i]);
    if (Sol==Inf) printf("Nu exista solutie");
    else printf("%d",Sol);  
    return 0;
}