#include<cstdio>
#define N 18
#define MULT -1
using namespace std;

int dp[1<<N][N];
int cost[N][N];

int minim(int a,int b){
    if (a==-1) return b;
    if (b==-1) return a;
    return (a<b) ? a : b;
}

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

    scanf ("%d%d",&n,&m);

    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            cost[i][j]=-1;
        cost[i][i]=0;
    }

    for(i=1;i<=m;i++){
        int x,y,c;

        scanf ("%d%d%d",&x,&y,&c);
        cost[x][y]=c;
    }

    for(j=0;j<(1<<n);j++)
        for(i=0;i<n;i++)
            dp[j][i]=-1;
    dp[1][0]=0;

    for(j=3;j<(1<<n);j+=2)
        for(i=1;i<n;i++)
            if (((1<<i)&j)!=0){
                int l,mask=(j^(1<<i));

                for(l=0;l<n;l++)
                    if (dp[mask][l]!=-1 &&cost[l][i]!=-1) dp[j][i]=minim(dp[j][i],dp[mask][l]+cost[l][i]);
            }

    int ans=-1;
    for(i=0;i<n;i++)
        if (dp[(1<<n)-1][i]!=-1 &&cost[i][0]!=-1) ans=minim(ans,dp[(1<<n)-1][i]+cost[i][0]);

    if (ans==-1) printf ("Ne exista solutie");
    else printf ("%d",ans);

    return 0;
}