#include <cstdio>
#include <vector>
#include <algorithm>

#define MAXN 18
#define INF 0x3f3f3f3f

using namespace std;

vector <int> G[MAXN];

int n, m, d[(1<<MAXN)][MAXN], cost[MAXN][MAXN];
bool seen[(1<<MAXN)][MAXN];

int solve(int mask, int node)
{
    if(seen[mask][node])
        return d[mask][node];

    int i, son;
    seen[mask][node] = 1;
    for(i=0; i<G[node].size(); ++i) {
        son = G[node][i];
        if(mask & (1<<son)) {
            if(son == 0 && mask != (1<<node) + 1) continue;
            d[mask][node] = min(d[mask][node], cost[son][node] + solve(mask - (1<<node), son));
        }
    }

    return d[mask][node];
}


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

    int i, j, x, y, z;

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

    for(i=0; i<n; ++i)
        for(j=0; j<n; ++j)
            cost[i][j] = INF;

    for(i=0; i<(1<<n); ++i)
        for(j=0; j<n; ++j)
            d[i][j] = INF;

    for(i=1; i<=m; ++i) {
        scanf("%d%d%d", &x, &y, &z);
        G[y].push_back(x);
        cost[x][y] = z;
    }

    d[1][0] = 0;
    seen[1][0] = 1;

    for(i=0; i<G[0].size(); ++i)
        d[(1<<n)-1][G[0][i]] = solve((1<<n)-1, G[0][i]);

    int answer = INF;
    for(i=1; i<n; ++i)
        if(cost[i][0] != INF)
            answer = min(answer, d[(1<<n)-1][i] + cost[i][0]);

    if(answer == INF)
        printf("Nu exista solutie");
    else printf("%d", answer);

    return 0;
}