#include <cstdio>
#include <algorithm>

using std::min;

const int MAX_N = 18;
const int INF = 0x3F3F3F3F;

int cost[MAX_N][MAX_N];
int d[1 << MAX_N][MAX_N];
int n;

int go(int mask, int prev) {
    if (d[mask][prev]) {
        return d[mask][prev];
    }
    int q = INF;
    if (mask == (1 << n) - 1) {
        if (cost[prev][0]) {
            q = cost[prev][0];
        }
    } else {
        for (int i = 0; i < n; i++) {
            if (cost[prev][i] && !((mask >> i) & 1)) {
                q = min(q, cost[prev][i] + go(mask ^ (1 << i), i));
            }
        }
    }
    return d[mask][prev] = q;
}

int main(void) {
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    int m, u, v, c;

    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &c);
        cost[u][v] = c;
    }
    fclose(stdin);

    c = go(1, 0);

    if (c == INF) {
        puts("Nu exista solutie");
    } else {
        printf("%d\n", c);
    }
    fclose(stdout);
    return 0;
}