#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];
    });
    auto pr = [&] (vector<vector<int>>V) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cout << V[i][j] << ' ';
            }

            cout << endl;
        }

        cout << endl;
    };


    int ans = 1e9;
    priority_queue<State>pq;
    pq.push (State ({1, 0, 0}));

    function<void (int, int, int)>Back = [&] (int mask, int last, int cost) {
        if (cost >= ans)
            return;

        if (mask == (1 << n) - 1) {
            if (init[last][0] != INF)
                ans = min (ans, cost + init[last][0] );

            return;
        }

        int lb = 0;
        bool bad = 0;

        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i))
                continue;

            int mn = INF;

            for (int j = 0; j < n; ++j) {
                if (! (mask & (1 << j)))
                    mn = min (mn, init[i][j]);
            }

            mn = min (mn, init[i][0]);

            if (mn != INF)
                lb += mn;

            mn = INF;

            for (int j = 0; j < n; ++j) {
                if (! (mask & (1 << j)))
                    mn = min (mn, init[j][i]);
            }

            mn = min (mn, init[last][i]);

            if (mn != INF)
                lb += mn;
            else
                bad = 1;
        }

        lb >>= 1;

        if (cost + lb >= ans)
            return;

        for (int i : L[last]) {
            if (mask & (1 << i))
                continue;

            if (init[last][i] == INF)
                continue;

            Back (mask | (1 << i), i, cost + init[last][i]);
        }
    };
    Back (1, 0, 0);

    cout << ans;
}