#include <iostream>
#include <fstream>
#include <vector>
#define maxN 20
#define MAX 262150
#define inf 100000000


using namespace std;

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

vector <int> v[maxN];
int n, m, Cost[maxN][maxN], D[MAX][maxN];

void initCost () {
    for (int i = 0; i < n-1; ++i) {
        for (int j = 0; j < n; ++j)
            Cost[i][j] = inf;
    }
}

void citire () {
    int x, y;
    for (int i = 0; i < m; ++i) {
        fin >> x >> y;
        v[y].push_back(x);
        fin >> Cost[x][y];
    }
}

void initD () {
    for (int i = 0; i < (1<<n); ++i) {
        for (int j = 0; j < n; ++j) {
            D[i][j] = inf;
        }
    }
    D[1][0] = 0;
}

int main () {
    fin >> n >> m;
    initCost();
    citire();
    initD();
    for (int i = 0; i < (1<<n); ++i) {
        for (int j = 0; j < n; ++j) {
            if (i & (1<<j)) {
                int size = v[j].size();
                for (int k = 0; k < size; ++k) {
                    if (i & (1<<v[j][k])) {
                        D[i][j] = min(D[i][j], D[i ^ (1<<j)][  v[j][k]] + Cost[ v[j][k] ][j]);
                    }
                }
            }
        }
    }
    int sol = inf, size = v[0].size();
    for (int i = 0; i < size; ++i) {
        sol = min(sol, D[(1<<n) - 1][v[0][i]] + Cost[v[0][i]][0]);
    }
    if (sol == inf) {
        fout << "Nu exista solutie";
    }
    else
        fout << sol;
}