#include<cstdio>
#include<string>
#include<cstring>

using namespace std;

#ifdef HOME
const string inputFile = "input.txt";
const string outputFile = "output.txt";
#else
const string problemName = "hamilton";
const string inputFile = problemName + ".in";
const string outputFile = problemName + ".out";
#endif

typedef pair<int, int> PII;
const int INF = (1 << 30);
const int NMAX = 18 + 1;

int N, M, sol;
PII E[NMAX*NMAX];
int DP[(1 << 18) + 5][NMAX];
int C[NMAX][NMAX];

int dp(int mask, int x) {
    if(DP[mask][x])
        return DP[mask][x];

    if((!mask) || ((1 << x) == mask && x != 0))
        return INF;

    if(mask == 1 && x == 0)
        return 0;

    int i;

    DP[mask][x] = INF;

    for(i = 0; i < N; i++)
        if(i != x && (mask & (1 << i)) && C[i][x])
            DP[mask][x] = min(DP[mask][x], dp(mask ^ (1 << x), i) + C[i][x]);

    return DP[mask][x];
}

int main() {
    int i, x, y, z, mask;

    freopen(inputFile.c_str(), "r", stdin);
    freopen(outputFile.c_str(), "w", stdout);

    scanf("%d%d", &N, &M);

    for(i = 1; i <= M; i++) {
        scanf("%d%d%d", &x, &y, &z);
        E[i] = make_pair(x, y);
        C[x][y] = z;
    }

    mask = (1 << N) - 1;
    sol = INF;

    for(i = 0; i < N; i++)
        if(C[i][0])
            sol = min(sol, dp(mask, i) + C[i][0]);

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

    return 0;
}