#include<cstdio>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<bitset>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<unordered_map>

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

const int nmax = 20;
const int lmax = (1 << 18) + 5;
const int inf = (1LL << 31) - 1;

int n, m, x, y, z, lim, i, j, sol;
int c[nmax][nmax], dp[lmax][nmax];

vector<int> v[nmax], g[nmax];

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

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

    for (; m; m--) {
        scanf("%d%d%d", &x, &y, &z);
        v[x].push_back(y);
        g[y].push_back(x);
        c[x][y] = z;
    }

    lim = 1 << n;

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

    dp[1][0] = 0;

    for (i = 1; i < lim; i++)
        for (j = 0; j < n; j++)
            if (dp[i][j] != inf)
                if ((1 << j) & i)
                    for (auto it : v[j])
                        if (((1 << it) & i) == 0)
                            dp[i + (1 << it)][it] = min(dp[i + (1 << it)][it], dp[i][j] + c[j][it]);

    sol = inf;
    for (auto it : g[0])
        if (dp[lim - 1][it] != inf)
            sol = min(sol, dp[lim - 1][it] + c[it][0]);

    if (sol == inf) printf("Nu exista solutie\n");
    else printf("%d\n", sol);

    return 0;
}