using namespace std;
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#define oo 0x3f3f3f3f
#define sfor(alfa,start,beta)  for(int alfa=start;alfa<=beta;++alfa)
ofstream fout("hamilton.out");
int N,minim=oo,m[10][10],per[10],M;

void solve()
{int ok,i,sum;
    for(i=0;i<=N-1;i++)
      per[i]=i;
    do
    {ok=1;
    sum=0;
        sfor(j,0,N-2)
           if(m[per[j]][per[j+1]]!=oo)
             sum+=m[per[j]][per[j+1]];
             else
              {
                  ok=0;
                  break;
              }
        if(m[per[N-1]][per[0]]!=oo)
            sum+=m[per[N-1]][per[0]];
            else
            ok=0;
           if(ok==1)
             if(sum<minim)
             minim=sum;

    }
    while(next_permutation(per,per+N));
    if(minim==oo)
      //fout<<"Nu exista solutie";
      //else
      fout<<minim;

}

void cit()
{int x,y,c,i;
  ifstream fin("hamilton.in");
  memset(m,oo,sizeof(m));
  fin>>N>>M;
  for(i=1;i<=M;i++)
  {
      fin>>x>>y>>c;
      m[x][y]=m[y][x]=c;

  }

  fin.close();


}

int main()
{
    cit();
    solve();
    fout.close();
    return 0;
}