#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<pair<int, int>>* g, * gt;
vector<int> h;
vector<bool> viz;
int n;
vector<vector<int>> c;

int bt(int u,int config) {
    //cout << u << ' ' << config << ' ' << c[u][config] << '\n';
    if (c[u][config] != -1) return c[u][config];
    if (u == 0) {
        if (config == 1) {
            c[u][config] = 0;
            return 0;
        }
        else {
            c[u][config] = 1e9;
            return 1e9;
        }
    }
    int min = 1e9;
    for (auto v : gt[u]) {
        //cout << v.first << '\n';
        if (((1 << v.first) & config) == (1 << v.first)) {
            int r = bt(v.first, config ^ (1 << u)) + v.second;
            if (r < min)
                min = r;
        }
    }
    c[u][config] = min;
    return min;

}

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

    int m;
    fin >> n >> m;
    g = new vector<pair<int,int>>[n + 1];
    gt = new vector<pair<int, int>>[n + 1];
    c.resize(n + 1);
    viz.resize(n + 1, false);
    while (m--) {
        int x, y, z;
        fin >> x >> y >> z;
        g[x].push_back({ y,z });
        gt[y].push_back({ x,z });
    }

    int min = 1e9;
    for (auto v : gt[0]) {
        for (int i = 0;i < c.size();++i)
            c[i].resize((1 << n) + 5, -1);
        int r = bt(v.first, (1 << n) - 1) + v.second;
        if (r < min) min = r;
    }
    if (min == 1e9)
        fout << "Nu exista solutie";
    else fout << min;

    delete[] g;

    return 0;
}