#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int i,n,m,cost[20][20],x,y,c[300000][20],sol,j,k,qq;
vector<int>v[20];
int main()
{fin>>n>>m;
 for(i=0;i<=n;i++)
    {for(j=0;j<=n;j++)
        cost[i][j]=1000000000;
    }
 for(i=1;i<=m;i++)
    {fin>>x>>y>>qq;
     cost[x][y]=qq;
     v[y].push_back(x);
    }
 for(i=0;i<(1<<n);i++)
    {for(j=0;j<n;j++)c[i][j]=1000000000;
    }
 c[1][0]=0;
 for(i=0;i<(1<<n);i++)
    {for(j=0;j<n;j++)
        if(i&(1<<j))
          {for(k=0;k<v[j].size();k++)
              {if(i&(1<<v[j][k]))
                  {c[i][j]=min(c[i][j],c[i^(1<<j)][v[j][k]]+cost[v[j][k]][j]);
                  }
              }
          }
    }
 sol=1000000000;
 for(i=0;i<v[0].size();i++)
    {sol=min(sol,c[(1<<n)-1][v[0][i]]+cost[v[0][i]][0]);
    }
    if(sol==1000000000)fout<<"Nu exista solutie";
      else fout<<sol;
}