#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=1000000000;
int cost[22][22];
int dp[263000][21];
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    //memset(cost,1,sizeof(cost));
    for(int i=0; i<=20; ++i)
        for(int j=0; j<=20; ++j)
            cost[i][j]=INF;
    for(int i=1; i<=m; ++i)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        cost[x][y]=z;
    }
    //memset(dp,INF,sizeof(dp));
    for(int i=0; i<(1<<n); ++i)
        for(int j=0; j<n; ++j)
            dp[i][j]=INF;
    dp [1][0] = 0;
    for(int masca=1; masca<(1<<n); ++masca)
        for(int nod=0; nod<n; ++nod)
            for(int k=0; k<n; ++k)
                if(!(masca&(1<<k)))
                   dp[masca+(1<<k)][k]=min(dp[masca+(1<<k)][k],dp[masca][nod]+cost[nod][k]);
    int sol=INF;
    for(int nod=0; nod<n; ++nod)
    {
        if(cost[nod][0])
        {
            // printf("*%d*\n",nod);
            sol=min(sol,dp[(1<<n)-1][nod]+cost[nod][0]);
        }
    }
    if(sol==INF)
        printf("Nu exista solutie\n");
    else
        printf("%d\n",sol);
}