# include <fstream>
# include <vector>
# define INF 1000000000
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int d[20][(1<<18)],rv[(1<<18)],v[20][20],n,m,i,j,t,x,y,cost,val,sol;
int main () {
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>cost;
        v[x][y]=cost;
    }
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
            d[j][i]=INF;
    d[0][1]=0;
    for(i=2;i<(1<<18);i*=2)
        rv[i]=rv[i/2]+1;
    for(i=1;i<(1<<n);i++){
        if(i%2==0)
            continue;
        val=(i^((1<<n)-1));
        for(j=i;j>0;j-=(j&(-j))){
            x=rv[(j&(-j))];
            if(d[x][i]==INF)
                continue;
            for(t=val;t>0;t-=(t&(-t))){
                y=rv[(t&(-t))];
                if(v[x][y])
                    d[y][i+(1<<y)]=min(d[y][i+(1<<y)],d[x][i]+v[x][y]);
            }
        }
    }
    sol=INF;
    for(i=1;i<n;i++)
        if(v[i][0]&&sol>d[i][(1<<n)-1]+v[i][0])
            sol=d[i][(1<<n)-1]+v[i][0];
    if(sol==INF){
        fout<<"Nu exista solutie\n";
        return 0;
    }
    fout<<sol<<"\n";
    return 0;
}