#include <fstream>
#include <vector>

using namespace std;

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

#define NMAX 18
#define INF 20000000

int n, m, dp[NMAX][1 << NMAX];
vector<pair<int, int>> G[NMAX];

void citire() {
    f >> n >> m;
    int x, y, c;
    for (int i = 0; i < m; ++i) {
        f >> x >> y >> c;
        G[x].push_back({y, c});
    }
}

void initializare() {
    int dim = (1 << n);
    for (int i = 1; i < n; i++)
        for (int j = 2; j <= dim; j++)
            dp[i][j] = INF;
}

void dinamica() {
    //Plecare din nodul 0
    for (auto &nod: G[0])
        dp[nod.first][(1 << nod.first) + 1] = nod.second;

    int dim = (1 << n) - 1;
    for (int j = 2; j < dim; j++)
        for (int i = 1; i < n; ++i)
            if (dp[i][j] != INF)
                for (auto &nod: G[i])
                    if (!(j & (1 << nod.first)))
                        dp[nod.first][j | (1 << nod.first)] = min(dp[nod.first][j | (1 << nod.first)],
                                                                  dp[i][j] + nod.second);

    //Intoarcere in nodul 0
    int mini = INF;
    for (int i = 1; i < n; ++i)
        if (dp[i][dim] != INF)
            for (auto &nod: G[i])
                if (nod.first == 0) {
                    mini = min(mini, dp[i][dim] + nod.second);
                    break;
                }
    if (mini == INF)
        g << "Nu exista solutie";
    else
        g << mini;
}

int main() {
    citire();
    if (n == 1) {
        g << "Nu exista solutie";
        return 0;
    }
    initializare();
    dinamica();
    return 0;
}