#include <bits/stdc++.h>
using namespace std;

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

using edge_t = pair<int, int>;
vector<vector<edge_t>> graph;

struct SetHash {
    size_t operator()(const set<int>& s) const {
        size_t h = 0;

        for (int x: s) {
            h ^= hash<int>{}(x) + 0x9e3779b9 + (h << 6) + (h >> 2);
        }

        return h;
    }
};
unordered_map<set<int>, int, SetHash> memoisation;

int path(int src, int dst, set<int> &used, int n) {
    if (n <= 0) {
        if (src == dst)
            return 0;
        return 1e9;
    }
    if (src == dst) return 1e9;

    auto it = memoisation.find(used);
    if (it != memoisation.end()) return it->second;

    int best = 1e9;
    for (auto [next, cost]: graph[src]) {
        if (used.count(next) > 0) continue;

        used.insert(next);
        best = min(best, cost + path(next, dst, used, n - 1));
        used.erase(next);
    }
    return best;
}

int main() {
    int m, n;
    fin >> n >> m;
    graph.resize(n);

    for (int i = 0; i < m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        graph[x].push_back({y, c});
    }

    int best = 1e9;
    for (auto [next, cost]: graph[0]) {
        set<int> used{next};
        best = min(best, cost + path(next, 0, used, n - 1));
    }

    if (best == 1e9)
        fout << "Nu exista solutie";
    else
        fout << best;
}