#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 path_t {
    int src, dst;
    size_t hash = 0;
    
    bool operator==(const path_t& other) const {
        return src == other.src && dst == other.dst && hash == other.hash;
    }

    bool contains_node(int node) const {
        return (hash & (1 << node));
    }
    
    void insert_node(int node) {
        hash |= (1 << node);
    }

    void erase_node(int node) {
        hash &= ~(1 << node);
    }
};

struct path_hash {
    size_t operator()(const path_t& s) const {
        size_t h = hash<int>{}(s.hash);

        h ^= hash<int>{}(s.src) + 0x9e3779b9 +
             (h << 6) + (h >> 2);

        h ^= hash<int>{}(s.dst) + 0x9e3779b9 +
             (h << 6) + (h >> 2);

        return h;
    }
};
unordered_map<path_t, int, path_hash> memoisation;

int get_path(path_t &path);

int get_memo_path(path_t &path) {
    auto it = memoisation.find(path);
    if (it != memoisation.end()) return it->second;

    int val = get_path(path);
    memoisation[path] = val;

    // printf("%d->%d %lb = %d\n", path.src, path.dst, path.hash, val);
    return val;
}

int get_path(path_t &path) {
    if (path.src == path.dst) {
        return ((path.hash == (1 << path.dst)) ? 0 : 1e9);
    }

    int best = 1e9;
    for (auto [next, cost]: graph[path.src]) {
        if (!path.contains_node(next)) continue;

        path_t new_path = path;
        new_path.erase_node(path.src);
        new_path.src = next;
        best = min(best, cost + get_memo_path(new_path));
    }
    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;
    path_t path;
    for (int i = 0; i < n; i++)
        path.insert_node(i);

    for (auto [next, cost]: graph[0]) {
        path.src = next;
        path.dst = 0;
        best = min(best, cost + get_memo_path(path));
    }

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