#include <bits/stdc++.h>

using namespace std;

const int N=18, Inf=1000000000;
int d[(1<<18)][18],v[N];
struct ii{
    int nod,cost;
};
vector <ii> G[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[b].push_back({a,c});
    }

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

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

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


    return 0;
}