#include <fstream>
#include <vector>
#include <climits>

using namespace std;

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

const int NMAX = 20;
const int INF = 18000001;
const int NMAX2 = 262144;

struct Muchie {
    int varf;
    int cost;
};

Muchie getMuchie (int a, int b)
{
    Muchie m;
    m.varf = a;
    m.cost = b;
    return m;
}

int n, m;

int graf[NMAX+1][NMAX+1];

int d[NMAX2+1][NMAX+1];

int minim (int a, int b)
{
    return a < b ? a : b;
}

void read()
{
    in >> n >> m;

    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        in >> x >> y >> z;

        graf[x][y] = z;
    }
}

void initializeaza()
{
    for (int i = 1; i < n; ++i) {
        d[1][i] = INF;
    }
}

void cicluHamilton()
{
    initializeaza();

    int numarPermutari = (1 << n) - 1;

    for (int i = 3; i <= numarPermutari; i += 2) {
        d[i][0] = INF;
        for (int j = 1; j < n; ++j) {
            d[i][j] = INF;
            int j2 = (1 << j);

            if (i & j2) {
                int prim = i ^ j2;

                for (int k = 0; k < n; ++k) {
                    int k2 = (1 << k);

                    if (graf[k][j] != 0 and (prim & k2) and j != k) {
                        d[i][j] = minim (d[i][j], d[prim][k] + graf[k][j]);
                    }
                }
            }
        }
    }

    int sol = INF;
    for (int i = 1; i < n; ++i) {
        if (graf[i][0] != 0) {
            sol = minim (sol, d[numarPermutari][i] + graf[i][0]);
        }
    }

    if (sol == INF) {
        out << "Nu exista solutie\n";
    } else {
        out << sol << "\n";
    }
}

int main()
{
    read();
    cicluHamilton();

    return 0;
}