#include <fstream>
#define NMAX 100
#define INF 1000000000
using namespace std;

int n,m;
int a[NMAX][NMAX];
bool uz[NMAX];
int t[NMAX], tmin[NMAX];
int lgt, lgmin;

void citire();
void afisare();
void bkt(int k);
int main()
{
    citire();
    t[1]=1; uz[1]=1;
    bkt(2);
    afisare();
    return 0;
}
void citire()
{
    ifstream fin("hamilton.in");
    int i,x,y,lg;
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>x>>y>>lg;
        a[x+1][y+1]=lg;
    }
}
void afisare()
{
    int i;
    ofstream fout("hamilton.out");
   if(lgmin==INF)
        fout<<"Nu exista solutie\n";
   else{
        fout<<lgmin<<'\n';

       }
       fout.close();
}
void bkt(int k)
{
    int i;
    if(k-1==n)
    {
        if(a[t[n]][1]) // pot sa revin
        {
            if(lgt+a[t[n]][1]<lgmin)
            {
                lgmin=lgt+a[t[n]][1];
                for(i=1;i<=n;i++)
                    tmin[i]=t[i];
            }
        }
    }
    else// nu e complet traseul
    for(i=1;i<=n;i++)
    if(!uz[i]&& a[t[k-1]][i])
        {
        t[k]=i;
        lgt+=a[t[k-1]][i];
    uz[i]=1;
    bkt(k+1);
    uz[i]=0;
        lgt-=a[t[k-1]][i];
        }
}