#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;


struct State {
    int mask, last, cost;
    bool operator< (const State &that) const {
        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;
    };
    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);
    function<void (int, int, int, vector<vector<int>>&)>Back = [&] (int took, int last, int cost, vector<vector<int>>&C) {
        if (cost + upperB (C) >= ans)
            return;

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


        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);
            Back (took + 1, nxt, new_cost, NC);
        }
    };
    Back (1, 0, start, init);

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