#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;


struct State {
    vector<vector<int>>C;
    int last, took, cost;
    bool operator< (const State &that) const {
        if(cost == that.cost)
            return took>that.took;
        return cost> that.cost;
    }
};
int main() {
    ifstream cin ("hamilton.in");
    ofstream cout ("hamilton.out");

    int n, m;
    cin >> n >> m;

    vector<vector<int>>init (n, vector<int> (n, INF));

    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        init[x][y] = z;
    }

    vector<vector<int>>L (n);

    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < n; ++j)
            if (init[i][j] != INF)
                L[i].push_back (j);


    }

    for (int i = 0; i < n; ++i)
        sort (L[i].begin(), L[i].end(), [&] (const int &a, const int &b) {
        return init[i][a]  < init[i][b];
    });

    int ans = INF;

    auto upperB = [&] (const vector<vector<int>>&C) {
        int delta = 0;
        int gt = 0;

        for (int i = 0; i < n; ++i) {
            int mn1 = INF, mn2 = INF;

            for (int j = 0; j < n; ++j) {
                mn1 = min (mn1, C[i][j]);
                mn2 = min (mn2, C[j][i]);
            }

            if (i == 0 && mn2 == INF)
                return INF;

            if (mn1 != INF)
                delta += mn1;

            if (mn2 != INF)
                delta += mn2;

        }


        return delta / 2;
    };

    auto Reduction = [&] (vector<vector<int>>&C) {
        int delta = 0;

        for (int i = 0; i < n; ++i) {
            int mn = INF;

            for (int j = 0; j < n; ++j)
                if (C[i][j] < mn)
                    mn = C[i][j];


            if (mn != INF) {
                delta += mn;

                for (int j = 0; j < n; ++j)
                    if (C[i][j] != INF)
                        C[i][j] -= mn;
            }

        }

        for (int j = 0; j < n; ++j) {
            int mn = INF;

            for (int i = 0; i < n; ++i) {
                mn = min (mn, C[j][i]);
            }

            if (mn != INF) {
                delta += mn;

                for (int i = 0; i < n; ++i)
                    if (C[j][i] != INF)
                        C[j][i] -= mn;
            }

        }

        return delta;
    };

    int start = Reduction (init);
    priority_queue<State>pq;
    pq.push (State{init, 0, 1, start});

    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();
        int cost = cur.cost;
        auto C = cur.C;
        int took = cur.took;
        int last = cur.last;

        if (cost >= ans)
            break;

        if (cost + upperB (C) >= ans)
            continue;


        if (took == n) {
            ans = min (ans, cost);
            continue;
        }


        for (int nxt : L[last]) {
            if (C[last][nxt] == INF)
                continue;

            vector<vector<int>>NC = C;

            for (int i = 0; i < n; ++i) {
                NC[last][i] = INF;
                NC[i][nxt] = INF;
            }

            NC[nxt][last] = INF;

            int new_cost = cost + C[last][nxt] + Reduction (NC);
            pq.push (State{NC, nxt, took + 1, new_cost});
        }
    }


    if (ans == INF)
        cout << "Nu exista solutie";
    else
        cout << ans;
}