#include<cstdio>
#include<vector>
#define INF 2000000000
using namespace std;
vector< pair<int,int> >L[50];
int n,m,a,b,c,vmin,i,j,k,v[100],s[300000][20];
FILE *f,*g;
int main(){
    f=fopen("hamilton.in","r");
    g=fopen("hamilton.out","w");
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(f,"%d%d%d",&a,&b,&c);
        L[a].push_back(make_pair(b,c));
    }
    for(i=1;i<=(1<<n);i++){
        for(j=0;j<n;j++){
            s[i][j]=INF;
        }
    }
    s[1][0]=0;
    for(i=3;i<=(1<<n);i+=2){
        for(j=0;j<n;j++){
            if(i&(1<<j)){
                for(k=0;k<L[j].size();k++){
                    a=L[j][k].first;
                    if( (i&(1<<a)) && s[i][j]>s[i-(1<<j)][a]+L[j][k].second ){
                        s[i][j]=s[i-(1<<j)][a]+L[j][k].second;
                    }
                }
            }
        }
    }
    vmin=INF;
    for(i=0;i<L[0].size();i++){
        if(vmin>s[ (1<<n)-1 ][ L[0][i].first ]+L[0][i].second)
            vmin=s[ (1<<n)-1 ][ L[0][i].first ]+L[0][i].second;
    }
    if(vmin!=INF){
        fprintf(g,"%d",vmin);
    }
    else{
        fprintf(g,"Nu exista solutie");
    }
    fclose(f);
    fclose(g);
    return 0;
}