#include <fstream>
#define VMAX 20
#define mare 999999999
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int mapa[VMAX][VMAX], track[VMAX], minTrack[VMAX], n, m, lg, lgmin=mare;
bool uz[VMAX];

void citire();
void generare(int k);
void afisare();

int main()
{
    citire();
    track[1]=1;
    uz[1]=1;
    generare(2);
    afisare();
    return 0;
}

void citire()
{
   int i, x, y, lg;
   fin >> n>> m;
   for (i=1; i<=m; i++)
   {
      fin >> x>> y>> lg;
      mapa[x+1][y+1]=lg;
   }
}

void generare(int k)
{
   int i;
   if (lg>=lgmin) return;
   if (k==n+1)
   {
      if (mapa[track[n]][1])
          if (lg+mapa[track[n]][1]<lgmin)
             {
              for (i=1; i<=n; i++) minTrack[i]=track[i];
              lgmin=lg+mapa[track[n]][1];
             }
   }
   else
   for (i=2; i<=n; i++)
         {
            if ((!uz[i])&&(mapa[track[k-1]][i]))
            {
               lg+=mapa[track[k-1]][i];
               uz[i]=1;
               track[k]=i;
               generare(k+1);
               uz[i]=0;
               lg-=mapa[track[k-1]][i];
            }
         }
}

void afisare()
{
   if (lgmin<mare) fout << lgmin;
     else fout << "Nu exista solutie";
}