#include <bits/stdc++.h>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int NMax = 18;
const int oo = 1e9;
vector <int> G[NMax+5];
int N, M, Cost[NMax+5][NMax+5], DP[(1<<NMax)+5][NMax+5];

void Read() {
    in >> N >> M;
    for(int i = 1, x ,y, c; i <= M; i++) {
        in >> x >> y >> c;
        G[y].push_back(x);
        Cost[x][y] = c;
    }
}

void Solve() {
    for(int i = 0; i < (1 << N); i++)
        for (int j = 0; j < N; j++)
            DP[i][j] = oo;
    DP[1][0] = 0;

    for (int Conf = 1; Conf < (1<<N); Conf++)
        for (int i = 0; i < N; i++) {
            if (Conf & (1<<i))
                for (auto j : G[i]) {
                    if (Conf & (1<<j))
                        DP[Conf][i] = min(DP[Conf][i], DP[Conf^(1<<i)][j] + Cost[j][i]);
                }
    }
}

void Print() {
    int Sol = oo;
    for (auto i : G[0]) {
        Sol = min(Sol, DP[(1<<N)-1][i]+Cost[i][0]);
    }
    if (Sol == oo)
        out << "Nu exista solutie";
    else
        out << Sol;
}

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