#include<cstdio>
#include<vector>
#define inf 2000000000
using namespace std;
vector< pair<int,int> >L[100];
int n,m,a,b,c,i,j,nod,st,vmin,d[1<<18][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=0;i<1<<n;i++){
        for(j=0;j<n;j++){
            d[i][j]=inf;
        }
    }
    d[1][0]=0;
    for(st=3;st<1<<n;st+=2){
        for(nod=0;nod<n;nod++){
            if(st&(1<<nod)){
                for(i=0;i<L[nod].size();i++){
                    a=L[nod][i].first;
                    if(st&(1<<a)){
                        b=d[st-(1<<nod)][a]+L[nod][i].second;
                        if(d[st][nod]>b)
                            d[st][nod]=b;
                    }
                }
            }
        }
    }
    vmin=inf;
    for(i=0;i<L[0].size();i++){
        if(vmin>d[(1<<n)-1][L[0][i].first]+L[0][i].second)
            vmin=d[(1<<n)-1][L[0][i].first]+L[0][i].second;
    }
    if(vmin==inf)
        fprintf(g,"Nu exista solutie");
    else
        fprintf(g,"%d",vmin);

    fclose(f);
    fclose(g);
    return 0;
}