#include<bits/stdc++.h>
#define Dim 1<<28
using namespace std;
int n,st[100],ns,a[20][20],m,C[100][100],x[100],sol,ras=Dim;
int e_valid(int k)
{   int i;
    if(k>1) if(!a[st[k-1]][st[k]]) return 0;
             else
              for(int i=1;i<k;i++)
               if(st[i]==st[k])  return 0;
   if(k==n)
    if(!a[st[1]][st[k]]) return 0;
return 1;
}
void afisare(int k)
{
    int i;
    /*for(i=1;i<=k;i++)
        cout<<st[i];
    cout<<endl;*/
    ns++;
}
/*void backtr(int k)
{   int i,vef;
st[k]=-1;
    while(k>0)
    {
        if(st[k]<n-1)
        {
            st[k]++;
            if(e_valid(k)) if(k==n) afisare(n);
                           else st[++k]=-1;
        }
        else k--;

    }
}*/
void backtr(int k)
{   int i,vef;
st[k]=-1;
    while(k>0)
    { vef=0;
        while(st[k]<n-1 && !vef)
        {
            st[k]++;
            vef=e_valid(k);
        }
       if(vef==1) if(k==n) afisare(n);
        else st[++k]=-1;
        else k--;
    }
}
int e_valid2(int k)
{    int i;
    for(i=1;i<k;i++)
        if(x[i]==x[k]) return 0;
    return 1;
}
void aflu()
{  int j;
     sol=C[x[n]][x[1]];
     for(j=1;j<n;j++)  sol+=C[x[j]][x[j+1]];
      ras=min(ras,sol);
}
int bcktr(int k)
{
    int i;
    for(i=0;i<n;i++)
    {
        x[k]=i;
        if(e_valid2(k)) if(k==n) aflu();
        else bcktr(k+1);
    }

}

int main()
{
    int i,j,x,y;
    ifstream fin("hamiltonian.in");
    ofstream fout("hamiltonian.out");
    fin>>n>>m;
    for ( i=0; i<n; ++i)
        for ( j=0; j<n; ++j) C[i][j] = Dim;

    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        fin >> C[x][y];
        a[x][y]=1;
    }
    backtr(1);
    if(!ns) fout<<"Nu exista solutie";
    bcktr(1);
    cout<<ras;
}