#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int MAXN = 19;
const int INF = 1e9;

vector<int> g[MAXN];

int cost_muchii[MAXN][MAXN];
int costMinim[MAXN][1 << MAXN];
int costul_minim = INF;
int n, m;

int CicCostMin(int nod, int configuratie) {
    if (configuratie == (1 << n) - 1) {
        if (cost_muchii[nod][0] > 0)
            return cost_muchii[nod][0];
        return INF;
    }
    if (costMinim[nod][configuratie] != INF)
        return costMinim[nod][configuratie];

    int costOptim = INF;
    for (int j = 0; j < g[nod].size(); ++j) {
        int vecin = g[nod][j];
        if (!(configuratie & (1 << vecin))) {
            int next_conf = configuratie;
            next_conf |= (1 << vecin);
            int newCost = CicCostMin(vecin, next_conf);
            if (newCost != INF)
                costOptim = min(costOptim, newCost + cost_muchii[nod][vecin]);
        }
    }
    return costMinim[nod][configuratie] = costOptim;
}

int main() {
    in >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        in >> x >> y >> c;
        g[x].push_back(y);
        cost_muchii[x][y] = c;
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < (1 << n); ++j)
            costMinim[i][j] = INF;
    costul_minim = CicCostMin(0, 1);
    if (costul_minim != INF) out << costul_minim;
    else out << "Nu exista solutie";
    return 0;
}