#include <fstream>
#define VMAX 20
#define INF 999999999
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

int harta[VMAX][VMAX], track[VMAX], minTrack[VMAX], n, m, lg, lgmin=INF;
bool used[VMAX];

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

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

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

void generare(int k)
{
   int i;
   bool ok;
   if (k==n+1)
   {
      if (harta[track[n]][1])
          if (lg+harta[track[n]][1]<lgmin)
             {
              for (i=1; i<=n; i++) minTrack[i]=track[i];
              lgmin=lg+harta[track[n]][1];
             }
   }
   else
   for (i=2; i<=n; i++)
         {
            if ((!used[i])&&(harta[track[k-1]][i]))
            {
               lg+=harta[track[k-1]][i];
               used[i]=1;
               track[k]=i;
               generare(k+1);
               used[i]=0;
               lg-=harta[track[k-1]][i];
            }
         }
}

void afisare()
{
   int i;
   if (lgmin<INF) cout << lgmin;
      else cout << "Nu exista solutie";
   //for (i=1; i<=n+1; i++) cout << minTrack[i]<< ' ';
}