#include <iostream>
#include <cstdio>
#define maxn 19
#define maxb 262155
#include <vector>
#include <cstring>
#define inf 100000000
using namespace std;

int n,m;
vector <int > g[maxn];
int dp[maxb][maxn],cost[maxn][maxn];

void citire()
{
    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)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        cost[x][y]=c;
        g[y].push_back(x);
    }
}

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    ///memset(cost,inf,sizeof(cost));
    ///memset(dp,inf,sizeof(dp));

    citire();
    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<g[j].size();++k)
                    if (i & (1<<g[j][k]))
                        dp[i][j]=min(dp[i][j], dp[i xor (1<<j)][ g[j][k] ] + cost[ g[j][k] ][j]);
    int sol=inf;
    for (int i=0; i < g[0].size();++i)
        sol=min(sol,dp[(1<<n)-1][g[0][i]] + cost[g[0][i]][0]);
    if (sol==inf)
        printf("Nu exista solutie");
    else printf("%d",sol);

    return 0;
}