#include <cstdio>
#include <vector>
#define min(a,b) (a < b ? a : b)
#define NMAX 20
#define MAXX 262150
#define INF  100000000

using namespace std;

int n,m,x,y,c,sol;
int cost[NMAX][NMAX], dp[MAXX][NMAX];
vector<int>v[NMAX];

int main()
{
    freopen("hamilton.in", "r" ,stdin);
    freopen("hamilton.out", "w" ,stdout);
    scanf("%d%d",&n,&m);
    for(int i = 0; i < n; ++i)
        for(int j = 0 ; j < n; ++j) cost[i][j]=INF;

    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[y].push_back(x);
        cost[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;

    for(int i = 0 ; i < 1<<n; ++i)
        for(int j = 0; j < n; ++j)
        {
            if (i & (1<<j))
            {
                for(int 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]] + cost[v[j][k]][j]);

                }
            }
        }

    sol=INF;
    for(int t = 0; t < v[0].size(); ++t)
        sol=min(sol, dp[(1<<n) -1][v[0][t]] + cost[v[0][t]][0]);
    if (sol == INF) printf("Nu exista solutie\n");
        else printf("%d\n",sol);
    return 0;
}