#include <fstream>
#define NMAX 30
#define INF 100000000

using namespace std;

int a[NMAX][NMAX];
int n;
bool uz[NMAX];
int tmin[NMAX], t[NMAX];
int c, cmin=INF;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

void citire();
void afisare();
void gen(int);

int main()
{
    citire();
    t[1]=tmin[1]=1;
    gen(2);
    afisare();
    return 0;
}

void citire()
{int x, y, c, j, m;
 fin>>n>>m;
 for (j=0; j<m; j++)
     {
      fin>>x>>y>>c;
      a[x+1][y+1]=c;
     }
}

void gen(int k)
{int i;
 if (c>=cmin) return;
 if (k-1==n)
     {if (a[t[n]][1])
          if (cmin>c+a[t[n]][1])
              {cmin=c+a[t[n]][1];
               //for (i=2; i<=n; i++) tmin[i]=t[i];
               }
      }
      else
      for (i=2; i<=n; i++)
          if (!uz[i] && a[t[k-1]][i])
             {
              t[k]=i;
              uz[i]=1;
              c+=a[t[k-1]][i];
              gen(k+1);
              uz[i]=0;
              c-=a[t[k-1]][i];
             }
}

void afisare()
{int i;
 if (cmin==INF) fout<<"Nu exista solutie\n";
     else
     {
       fout<<cmin<<'\n';
       //for (i=1; i<=n; i++) fout<<tmin[i]-1<<' ';
       }
}