#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int NMAX=18;
const int Inf=0x3f3f3f3f;
int N,M,Cost[NMAX][NMAX],Din[NMAX][1<<NMAX];
vector<int> G[NMAX];
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 ret=Inf;
      vector<int>::iterator it;
      for (it=G[x].begin();it!=G[x].end();++it)
           if ((1<<(*it))&k)
             ret=min(ret,Cost[x][*it]+Calc(*it,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;
          G[i].push_back(j);
    }
   
    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;
}