#include <bits/stdc++.h>

#define MAXN        18
#define MAXBITS 262144
#define INF 2000000005

int N, M;
std::vector <int> ADC[MAXN];
int Cost[MAXN][MAXN];
int DP[MAXN][MAXBITS];

inline void AddEdge(int X, int Y, int W) {
    ADC[X].push_back(Y);
    Cost[X][Y] = W;
}

std::ifstream In ("hamilton.in");
std::ofstream Out("hamilton.out");

void Citire() {
    In >> N >> M;
    for (int i=1, X, Y, W; i<=M; ++i)
        In >> X >> Y >> W, AddEdge(X, Y, W);
}

void Rezolvare() {
    for (int i=0, j; i<MAXN; ++i)
        for (j=0; j<MAXBITS; ++j)
            DP[i][j] = INF;

    for (int i=0; i<N; ++i)
        DP[i][0] = DP[i][1] = 0;
    int lim = (1<<N)-1;

    for (int bits=1, i; bits<=lim; ++bits)
        for (i=0; i<N; ++i) if (bits & (1<<i))
            for (auto Edge:ADC[i]) if (bits & (1<<Edge))
                DP[i][bits] = std::min(DP[i][bits], DP[Edge][bits ^ (1<<i)] + Cost[i][Edge]);

    int Ans = INF;
    for (int i=1; i<N; ++i) if (Cost[0][i])
        Ans = std::min(Ans, DP[i][lim] + Cost[0][i]);

    if (Ans == INF) Out << "Nu exista solutie\n";
    else Out << Ans << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}