#include<cstdio>
#include<algorithm>
#include<cmath>
#define M 2000000000
using namespace std;
FILE *f=fopen("hamilton.in","r");
FILE *g=fopen("hamilton.out","w");
int a[18][18],n,x,y,z,v[19],ok,s,m;
int minim=M;
int ciclu(int &s)
{
    int i;
    v[n]=v[0];
    for(i=0;i<n;i++)
        if(a[v[i]][v[i+1]])
            s+=a[v[i]][v[i+1]];
        else return 0;
    return 1;
}
int main()
{
    int i;
    fscanf(f,"%d%d",&n,&m);
    for(i=0;i<m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&z);
        a[x][y]=z;
    }
    for(i=0;i<n;i++)
        v[i]=i;
    while(next_permutation(v,v+n))
    {
        s=0;
        ok=ciclu(s);
        if(ok==1)
            minim=min(minim,s);
    }
    if(minim==M)
        fprintf(g,"Nu exista solutie");
    else fprintf(g,"%d",minim);
    return 0;
}