#include <fstream>
#include <climits>
#define VMAX 20
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int mapa[VMAX][VMAX], sol[VMAX], sol2[VMAX], n, m, lg, lgmin=INT_MAX;
bool uz[VMAX];
void citire();
void gen(int k);
int main()
{
    citire();
    sol[1]=1;
    uz[1]=1;
    gen(2);
    if (lgmin<INT_MAX)
        fout<<lgmin-1;
    else fout<<"Nu exista solutie";
    return 0;
}
void citire()
{
    int x,y,i;
    fin>>n>>m;
    for (i=1; i<=m; i++)
        {
         fin>>x>>y>>lg;
         mapa[x+1][y+1]=lg;
        }
}
void gen(int k)
{
   int i;
  if (lg>=lgmin)
    return;
   if (k==n+1)
   {
      if (mapa[sol[n]][1])
          if (lg+mapa[sol[n]][1]<lgmin)
             {
              for (i=1; i<=n; i++)
                    sol2[i]=sol[i];
              lgmin=lg+mapa[sol[n]][1];
             }
   }
   else
   for (i=2; i<=n; i++)
         {
            if ((!uz[i])&&(mapa[sol[k-1]][i]))
            {
               lg+=mapa[sol[k-1]][i];
               uz[i]=1;
               sol[k]=i;
               gen(k+1);
               uz[i]=0;
               lg-=mapa[sol[k-1]][i];
            }
         }
}