#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;
    }

    int resolve() const {
        return ((hash == (1UL << dst)) ? 0 : 1e9);
    }

    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 {
        return s.hash;
    }
};
int memoisation[18][18][1 << 18];

int get_path(path_t &path);

int get_memo_path(path_t &path) {
    int x = memoisation[path.src][path.dst][path.hash];
    if (x != 0) return x;

    int val = get_path(path);
    memoisation[path.src][path.dst][path.hash] = 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.resolve();

    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;
}