#include <cstdio>
#include <vector>
#define NMAX 262150
#define INF 100000005

using namespace std;
vector<int>v[50];
int mat[50][50],dp[NMAX][21];
int n,m,x,y,c,sol,i,j,k;

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[y].push_back(x);
        mat[x][y]=c;
    }
    for(int i = 0;  i < (1<<n); ++i)
        for(int j = 0; j < n; ++j) dp[i][j]= INF;
    dp[1][0]=0;
    //pentru fiecare drum
    for(i=0; i < (1<<n); ++i)
        for(j=0;j<n;++j)
        {
            if(i & (1<<j))
            {
                for(k=0;k<v[j].size();++k)
                {
                    if(i&(1<<v[j][k]))
                    {
                        dp[i][j]=min(dp[i][j],dp[i^(1<<j)][v[j][k]] + mat[v[j][k]][j]);
                    }
                }
            }
        }
    //adunam muchia de intoarcere
    sol=INF;
    for(int t=0;t<v[0].size();++t)
         sol = min(sol,dp[(1<<n)-1][v[0][t]] + mat[v[0][t]][0]);
    if(sol == INF) printf("Nu exista solutie\n");
        else printf("%d\n",sol);
    return 0;
}