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