#include <fstream>
#include <vector>
#include <set>
using namespace std;
int i,j,k,m,n,l,x,c,y,viz[100],solutie[100],noduri,costuri[19][19],cost,minim,a[100],poz,ordine[100];
vector <int> T[100];
void zero()
{
    int i;
    for(i=1;i<n+1;i++)
        ordine[i]=0;
}
void calc()
{
  int j;
  int i;
  cost=0;
  for(i=0;i<T[a[n]].size();i++)
     if(T[a[n]][i]==a[1])
  {
     for(j=1;j<n;j++)
      cost=cost+costuri[a[j]][a[j+1]];
      cost=cost+costuri[a[n]][a[1]];
      if(cost<minim) minim=cost;
    break;
  }
}
void dfs()
{
   a[1]=1;
   viz[a[1]]=1;
   zero();
   noduri=1;
   k=2;
   while(k>1)
   {
      if(ordine[a[k-1]]<T[a[k-1]].size())
              {
                 a[k]=T[a[k-1]][ordine[a[k-1]]];
                 ordine[a[k-1]]++;
                 poz=a[k];
                 if(viz[poz]==0) {if(k<n){ viz[poz]=1; k++;} noduri++;}
                 if(k==n&&viz[a[n]]==0) calc();
              }
     else
        {
         poz=a[k-1];
         if(viz[poz]==1) {viz[poz]=0; noduri--;}
         ordine[poz]=0;
         viz[a[k-1]]=0;
         a[k]=0; a[k-1]=0;
         k--;
        }
   }


}
int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin>>n>>m;
    minim=1000000000;
    for(i=1;i<m+1;i++)
      {
          fin>>x>>y>>c;
          costuri[x+1][y+1]=c;
          T[x+1].push_back(y+1);
      }
         dfs();
    if(minim==1000000000) fout<<"Nu exista solutie";
    else  fout<<minim;
    fin.close();
    fout.close();
    return 0;
}