#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
using namespace std;

const char iname[] = "hamilton.in";
const char oname[] = "hamilton.out";

const int MAX_N = 18;

int C[1][1 << MAX_N][MAX_N];

inline int has_bit(int n, int i) {
    return (n >> i) & 1;
}

int main(void) {
    ifstream in(iname);
    int N, M;

    int cost[MAX_N][MAX_N];
    memset(cost, 0x3f3f3f3f, sizeof cost);

    assert(in >> N >> M);
    assert(1 <= N && N <= 18);
    assert(1 <= M && M <= N*(N-1));
    for (; M > 0; -- M) {
        int x, y, c;
        assert(in >> x >> y >> c);
        assert(0 <= x && x < N);
        assert(0 <= y && y < N);
        assert(1 <= c && c <= 1000000);
        cost[x][y] = c;
    }
    in.close();

    int i = 0;
    memset(C, 0x3f3f3f3f, sizeof C);
    C[i][1 << i][i] = 0;
    for (int j = 0; j < 1 << N; ++ j) {
        for (int k = 0; k < N; ++ k) if (has_bit(j, i) && has_bit(j, k)) {
            for (int v = 0; v < N; ++ v) if (has_bit(j, v))
                C[i][j][k] = min(C[i][j][k], C[i][j ^ (1 << k)][v] + cost[v][k]);
        }
    }
    int res = 0x3f3f3f3f;
    for (int k = 0; k < N; ++ k)
        res = min(res, C[i][(1 << N) - 1][k] + cost[k][i]);
    ofstream out(oname);
    if (res < 0x3f3f3f3f)
        out << res << "\n";
    else
        out << "Nu exista solutie\n";
    out.close();
    return 0;
}