#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 18 + 1 + 1;
const int INF = 0X3fffffff;

int n, m;
int cost[NMAX][NMAX];
int best[NMAX][1 << NMAX];


void citeste() {
    f >> n >> m;
    int a, b, c;
    for (int i = 1; i <= m; i++) {
        f >> a >> b >> c;
        a++; b++;
        cost[a][b] = c;
    }
}

int hamilton(int nod, int mask) {
    if (best[nod][mask] != 0) return best[nod][mask];
    if (mask == (1 << (n + 1)) - 2) {
        if (cost[nod][1] != 0) best[nod][mask] = cost[nod][1];
        else best[nod][mask] = INF;
        return best[nod][mask];
    }
    int aux;
    best[nod][mask] = INF;
    for (int i = 2; i <= n; i++) {
        if ((mask & (1 << i)) == 0 && cost[nod][i]) {
            aux = hamilton(i, mask | (1 << i));
            best[nod][mask] = min(best[nod][mask], aux + cost[nod][i]);
        }
    }
    return best[nod][mask];
}



int main() {
    citeste();
    int sol = hamilton(1, 1 << 1);
    if (sol == INF) g << "Nu exista solutie";
    else g << sol << '\n';
    g << '\n';
    return 0;
}