#include<cstdio>
#include<vector>
#define inf  1000000000

using namespace std;

int n,m,cost[30][30],dp[300000][20],i,j;
vector<int> a[30];

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

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

    for(i=0;i<n;++i)
        for(j=0;j<=n;++j) cost[i][j]=inf;

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

    for(i=1;i<=m;++i)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        a[y].push_back(x);
        cost[x][y]=c;
    }

    for(i=1;i<(1<<n);++i)
    {
        for(j=0;j<n;++j)
        if(i&(1<<j))
        {
            for(int k=0;k<a[j].size();++k)
            {
                int fiu=a[j][k];
                if(i&(1<<fiu))
                    dp[i][j]=min(dp[i][j],dp[i^(1<<j)][fiu]+cost[fiu][j]);
            }
        }
    }
    int mi=inf+2;
    for(i=1;i<n;++i)
        if(dp[(1<<n)-1][i]+cost[i][0])
        mi=min(mi,dp[(1<<n)-1][i]+cost[i][0]);

    if(mi==2000000000||mi==0) printf("Nu exista solutie\n");
    else printf("%d\n",mi);

    fclose(stdin);
    fclose(stdout);
    return 0;
}