#include <vector>
#include <fstream>
#include <algorithm>
#include <cassert>
#include <tuple>

using namespace std;

int main() {
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");

    int n, m; cin >> n >> m;
    vector<vector<int>> D(n, vector<int>(n, 1e8));
    for (int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        D[a][b] = c;
    }

    int ans = 2e9;
    vector<tuple<int, int, int, int>> beam, nbeam;
    for (int fst = 0; fst < n; ++fst) {
        beam.clear();
        beam.emplace_back(0, 1 << fst, fst, fst);
        int bw = 10000;
        for (int i = 1; i < n; ++i) {
            nbeam.clear();
            for (auto it : beam) {
                int cost, msk, last, fst; tie(cost, msk, last, fst) = it;
                for (int nxt = 0; nxt < n; ++nxt) {
                    if (msk & (1 << nxt)) continue;
                    int ncost = cost + D[last][nxt];
                    int nmsk = msk | (1 << nxt);
                    int nlast = nxt;
                    nbeam.emplace_back(ncost, nmsk, nlast, fst);
                }
            }
            if (nbeam.size() > bw) {
                nth_element(nbeam.begin(), nbeam.begin() + bw, nbeam.end());
                nbeam.resize(bw);
            }
            swap(beam, nbeam);
        }
        for (auto it : beam) {
            int cost, msk, last, fst; tie(cost, msk, last, fst) = it;
            assert(msk == (1 << n) - 1);
            ans = min(ans, cost + D[last][fst]);
        }
    }
    if (ans > n * 1e6) {
        cout << "Nu exista solutie" << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}