#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+2)
   {
      ok=1;
      for (i=1; i<=n; i++) if (!used[i])
      {
         ok=0;
         break;
      }
      if ((ok)&&(lg<lgmin)&&(track[n+1]==1))
      {
         for (i=1; i<=n+1; i++) minTrack[i]=track[i];
         lgmin=lg;
      }
   }
   else
   {
      if (k==n+1)
      {
         if (harta[track[k-1]][1])
         {
            track[k]=1;
            lg+=harta[track[k-1]][1];
            generare(k+1);
            lg-=harta[track[k-1]][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;
   cout << lgmin;
   //for (i=1; i<=n+1; i++) cout << minTrack[i]<< ' ';
}