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

using namespace std;

const int kMaxN = 18;
const int kMaxC = 1<<kMaxN;
const int oo = 1000000000;

vector<int> GT[kMaxN];
int N, DP[kMaxC][kMaxN], Cost[kMaxN][kMaxN], S;

int Memo(const int X, const int Conf) {
    if (DP[Conf][X] != -1)
        return DP[Conf][X];
    DP[Conf][X] = oo;
    for (vector<int>::iterator Y = GT[X].begin(); Y != GT[X].end(); ++Y)
        if (Conf&(1<<(*Y)))
            DP[Conf][X] = min(DP[Conf][X], Memo(*Y, Conf^(1<<X))+Cost[*Y][X]);
    return DP[Conf][X];
}

void Solve() {
    memset(DP, -1, sizeof(DP));
    DP[1][0] = 0;
    S = oo;
    for (vector<int>::iterator Y = GT[0].begin(); Y != GT[0].end(); ++Y)
        S = min(S, Memo(*Y, (1<<N)-1)+Cost[*Y][0]);
}

void Read() {
    freopen("hamilton.in", "r", stdin);
    int M; scanf("%d %d", &N, &M);
    for (; M; --M) {
        int X, Y; scanf("%d %d", &X, &Y);
        scanf("%d", &Cost[X][Y]);
        GT[Y].push_back(X);
    }
}

void Print() {
    freopen("hamilton.out", "w", stdout);
    if (S == oo)
        printf("Nu exista solutie\n");
    else
        printf("%d\n", S);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}