#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
const int nmax = 18;

int n , m , i , node , conf , ans;

int cost[nmax][nmax];
int dp[1<<nmax][nmax];

vector < int > g[nmax];

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

    scanf("%d %d", &n, &m);
    for (i = 1; i <= m; ++i)
    {
        int x , y;
        scanf("%d %d", &x, &y);

        g[x].push_back(y);

        scanf("%d", &cost[x][y]);
    }

    memset(dp , inf , sizeof(dp));

    dp[1][0] = 0;
    for (conf = 1; conf < (1 << n); ++conf)
        for (node = 0; node < n; ++node)
            if (conf & (1 << node))
                for (auto &it : g[node])
                {
                    if (conf & (1 << it)) continue;
                    dp[conf|(1<<it)][it] = min(dp[conf|(1<<it)][it] , dp[conf][node] + cost[node][it]);
                }

    conf = (1 << n) - 1; ans = inf;

    for (i = 0; i < n; ++i)
        if (cost[i][0]) ans = min(ans , dp[conf][i] + cost[i][0]);

    (ans == inf) ? printf("Nu exista solutie\n") : printf("%d\n", ans);

    return 0;
}