#include <fstream>
#include <climits>
#define NMAX 20
#define INF (1LL<<60)
using namespace std;

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

int N, M, ok;
long long A[NMAX][NMAX], cmin;
int x[NMAX], viz[NMAX];

void citire() {
    fin >> N >> M;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            A[i][j] = -1;

    int u, v;
    long long c;
    for (int i = 0; i < M; i++) {
        fin >> u >> v >> c;
        A[u][v] = c;
    }
}

void BACK(int k, long long cost) {
    if (cost >= cmin) return; // pruning simplu

    if (k == N) {
        if (A[x[N-1]][x[0]] != -1) {
            long long total = cost + A[x[N-1]][x[0]];
            if (total < cmin) {
                cmin = total;
                ok = 1;
            }
        }
        return;
    }

    for (int i = 1; i < N; i++) { // 0 e fixat ca start
        if (!viz[i] && A[x[k-1]][i] != -1) {
            viz[i] = 1;
            x[k] = i;
            BACK(k+1, cost + A[x[k-1]][i]);
            viz[i] = 0;
        }
    }
}

int main() {
    citire();

    for (int i = 0; i < N; i++) viz[i] = 0;

    cmin = INF;
    ok = 0;

    x[0] = 0;
    viz[0] = 1;

    BACK(1, 0);

    if (ok) fout << cmin << "\n";
    else fout << "Nu exista solutie\n";

    return 0;
}