#include <fstream>
#include <vector>

using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");

const int NMAX = 19,
XMAX = (1 << 18),
INF = (1 << 30);

int N, M, NN, Cost[NMAX][NMAX], C[XMAX][NMAX];

vector < int > G[NMAX];

void citire() {
    int x, y, i, j;
    in >> N >> M;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            Cost[i][j] = INF;

    for (i = 1; i <= M; ++i) {
        in >> x >> y;
        G[y].push_back(x);
        in >> Cost[x][y];
    }
    NN = (1 << N) - 1;
}


int calcul(int cfg, int j) {
    if (C[cfg][j] == -1) {
        C[cfg][j] = INF;
        for (int& x : G[j]) {
            if (cfg & (1 << x)) {
                if (x == 0 && cfg != (1 << j) + 1)
                    continue;
                C[cfg][j] = min(C[cfg][j], calcul(cfg ^ (1 << j), x) + Cost[x][j]);
            }
        }
    }
    return C[cfg][j];
}


int main() {

    int Sol = INF;
    citire();

    for (int i = 0; i <= NN; ++i)
        for (int j = 0; j <= N; ++j)
            C[i][j] = -1;

    C[1][0] = 0;

    for (int& nod : G[0])
        Sol = min(Sol, calcul(NN, nod) + Cost[nod][0]);

    if (Sol == INF)
        out << "Nu exista solutie";
    else
        out << Sol;

    return 0;
}