#include <cstdio>
#include <cstring>
using namespace std;
const int NMAX=18;
const int Inf=0x3f3f3f3f;
int N,M,Cost[NMAX][NMAX],Din[NMAX][1<<NMAX];
inline int min(int x,int y) {return x<y?x:y;}
int  Calc(int x,int k)
{
     k-=(1<<x);
     if (k==0) return 0;
     if (k==1 && Cost[x][0]>0) return 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));
      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;
}