using namespace std;
#include<fstream>
struct nod
{
  int vf;
  int cost;
  nod* next;
};  
int n,m,x[20],v[20],cost,costmin=2147483647;
nod *G[20];
void addarc(int,int,int);
void back(int);
void solutie();
int main()
{
  int i,xx,yy,zz;
  ifstream fin("hamilton.in");
  fin>>n>>m;
  for(i=1;i<=m;++i)
  {
    fin>>xx>>yy>>zz;
    addarc(xx,yy,zz);
  }
  x[0]=v[1]=1;
  back(1);
  ofstream fout("hamilton.out");
  fout<<costmin;
  return 0;
}
void back(int k)
{
  nod *p;
  if(k==n)
    solutie();
  else
    for(p=G[x[k-1]];p;p=p->next)
       if(v[p->vf]==0)
       {
         x[k]=p->vf;
         v[p->vf]=1;
         cost+=p->cost;
         back(k+1);
         cost-=p->cost;
         v[p->vf]=0;
       }  
}
void addarc(int i,int j,int c)
{
  nod *p=new nod;
  p->vf=j;
  p->cost=c;
  p->next=G[i];
  G[i]=p;
}
void solutie()
{
  int i;
  nod *p;
  for(p=G[x[n-1]];p;p=p->next)
     if(p->vf==x[0])
     {
       cost+=p->cost;
       i=p->cost;
       break;
     }  
  if(cost<costmin)
    costmin=cost;
  cost-=i;
}