#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

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

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

vector <int> GT[NMAX+1];

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

    for (int i=1; i<=M; i++) {
        f >> x >> y >> c;
        GT[y].push_back(x);
        Cost[x][y] = c;
    }
    NN = (1 << N) - 1;
}

void calcul() {
    for (int i=0; i<=NN; i++)
        for (int j=0; j<N; j++)
            C[i][j] = INF;
    //
    C[1][0] = 0;
    for (int i=0; i<=NN; i++)
        for (int j=0; j<N; j++)
            if(i & (1 << j))
                for (const auto &x : GT[j])
                    if (i & (1 << x))
                        C[i][j] = min(C[i][j], C[i^(1<<j)][x] + Cost[x][j]);
}

int main()
{
    int sol = INF;
    citire();
    calcul();
    for (const auto &nod : GT[0])
        sol = min(sol, C[NN][nod] + Cost[nod][0]);
    if (sol == INF)
        g << "Nu exista solutie";
    else
        g << sol;
    f.close();
    g.close();
    return 0;
}