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

    vector<tuple<int, int, int>> beam, nbeam;
    beam.emplace_back(0, 1 << 0, 0);
    vector<bool> seen((1 << n) * n, 0);
    int bw = 10000;
    for (int i = 1; i < n; ++i) {
        nbeam.clear();
        for (auto [cost, msk, last] : beam) {
            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);
            }
        }
        sort(nbeam.begin(), nbeam.end());
        beam.clear();
        for (auto [cost, msk, last] : nbeam) {
            if (seen[msk * n + last]) continue;
            seen[msk * n + last] = true;
            beam.emplace_back(cost, msk, last);
            if (beam.size() == bw) break;
        }
        for (auto [cost, msk, last] : beam)
            seen[msk * n + last] = false;
    }
    int ans = 2e9;
    for (auto [cost, msk, last] : beam) {
        assert(msk == (1 << n) - 1);
        ans = min(ans, cost + D[last][0]);
    }
    cout << ans << endl;

    return 0;
}