#include <iostream>
#include <fstream>

using namespace std;

#define NMAX 18
#define INFINIT 17000000

int cost[NMAX][NMAX];
int d[NMAX][1 << NMAX];

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

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

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

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

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

    for (int conf = 1; conf < (1 << n); ++conf) {
        for (int i = 0; i < n; ++i) {
            if (conf & (1 << i) && d[i][conf] < INFINIT) {
                for (int j = 0; j < n; ++j) {
                    if (cost[i][j] && !(conf & (1 << j))) {
                        d[j][conf | (1 << j)] = min(d[j][conf | (1 << j)], d[i][conf] + cost[i][j]);
                    }
                }
            }
        }
    }

    int raspuns = INFINIT;
    for (int i = 0; i < n; ++i) {
        if (cost[i][0])
            raspuns = min(raspuns, d[i][(1 << n) - 1] + cost[i][0]);
    }

    if (raspuns < INFINIT)
        fout << raspuns << "\n";
    else fout << "Nu exista solutie";

    return 0;
}