#include <iostream>
#include <fstream>

using namespace std;

#define NMAX 18
#define INFINIT (1 << 30)

int muchie[NMAX][NMAX];
long long cost[1 << NMAX][NMAX];

void afisBinar(int n)
{
    for (int i = 0; i < 5; ++i) {
        cout << ((n & (1 << i)) ? 1 : 0);
    }
    cout << "\n";
}

long long aflaCostCiclu(int ind, int conf, int n);

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");

    int n, m;
    fin >> n >> m;

    int x, y, c;
    while (m--) {
        fin >> x >> y >> c;
        muchie[x][y] = c;
    }

    for (int i = 1; i <= (1 << n) - 1; ++i)
        for (int j = 0; j < n; ++j)
            cost[i][j] = INFINIT;

    int start = 0;
    cost[1 << start][start] = 0;

    long long raspuns = aflaCostCiclu(start, (1 << n) - 1, n);
    if (raspuns < INFINIT)
        fout << raspuns;
    else fout << "Nu exista solutie";

    return 0;
}

long long aflaCostCiclu(int ind, int conf, int n)
{
    // cout << ind << " ";
    // afisBinar(conf);

    if (cost[conf][ind] >= INFINIT) {
        long long minim = INFINIT;
        for (int i = 0; i < n; ++i) {
            if (muchie[i][ind] && (conf & (1 << i))) {
                // cout << ind << ": primesc de la " << i << " cost total " << aflaCostCiclu(i, conf ^ (1 << i), n) + muchie[i][ind] << "\n";
                minim = min(minim, aflaCostCiclu(i, conf ^ (1 << i), n) + muchie[i][ind]);
            }
        }
        cost[conf][ind] = minim;
    }

    // cout << "gata " << ind << ": " << cost[conf][ind] << "\n";

    return cost[conf][ind];
}