#include <fstream>
#include <vector>
using namespace std;
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");
int n,m,a,b,c,t[23][23],d[1<<18][23],sol;
vector <int> v[23];
int main()
{
      f>>n>>m;
      for(int i=0;i<n;++i)
      {
            for(int j=0;j<n;++j) t[i][j]=2e9;
      }
      while(m--)
      {
            f>>a>>b>>c;
            t[a][b]=c;
            v[b].push_back(a);
      }
      for(int i=0;i<(1<<n);++i)
      {
            for(int j=0;j<n;++j) d[i][j]=2e9;
      }
      sol=2e9;
      d[1][0]=0;
      for(int i=1;i<(1<<n);++i)
      {
            for(int j=0;j<n;++j)
            {
                  if(i&(1<<j))
                  {
                        for(int k=0;k<v[j].size();++k)
                        {
                              if(i&(1<<v[j][k]))
                              {
                                    d[i][j]=min(d[i][j],d[i^(1<<j)][v[j][k]]+t[v[j][k]][j]);
                              }
                        }
                  }
            }
      }
      for(int i=0;i<v[0].size();++i) sol=min(sol,d[(1<<n)-1][v[0][i]]+t[v[0][i]][0]);
      if(sol==2e9)
      {
            g<<"Nu exista solutie";
      }
      else g<<sol;
      return 0;
}