#include <bits/stdc++.h>

using namespace std;

const int N=18, Inf=1000000000;
int d[18][(1<<18)],v[N];
struct ii{
    int nod,cost;
};
vector <ii> G[N];
vector <ii> t[N];

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    int n,m,l,i,j,a,b,c,k,x;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        G[a].push_back({b,c});
        t[b].push_back({a,c});
    }

    k=(1<<n)-1;
    for(j=0;j<=k;j++)
        for(i=0;i<n;i++) d[i][j]=Inf;

    d[0][1]=0;
    for(i=0;i<G[0].size();i++){
        x=G[0][i].nod;
        c=G[0][i].cost;
        d[x][1+(1<<x)]=c;
    }

    for(j=1;j<=k;j++){
        for(i=0;i<n;i++){
            if(j&(1<<i)){
                for(l=0;l<t[i].size();l++){
                    x=t[i][l].nod;
                    if(j&(1<<x)){
                        d[i][j]=min(d[i][j], d[x][j^(1<<i)]+t[i][l].cost);
                    }
                }
            }
        }
    }

    int Min=Inf;
    for(i=0;i<t[0].size();i++){
        x=t[0][i].nod;
        c=t[0][i].cost;
        Min=min(Min,d[x][k]+c);
    }
    if(Min==Inf) printf("Nu exista solutie\n");
    else printf("%d\n",Min);




    return 0;
}