#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


const int INF = (int)(1e9);

void upd(int &x, int y) {
    x = min(x, y);
}

int main() {
#ifdef HOME
    assert(freopen("in", "r", stdin));
#endif


    int n, m;
    while (cin >> n >> m) {
        vector<vector<int> > e(n, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            u--; v--;
            e[u][v] = e[v][u] = w;
        }

        /*vector<int> g(1 << n, INF);
        for (int mask = 0; mask < (1 << n); mask++) {
            if ((mask & 1) || (mask & (1 << (n - 1)))) continue;
            for (int smask = mask;; smask = (smask - 1) & mask) {
                int cur = 0;
                vector<int> tp(n);
                tp[0] = 1;
                tp[n - 1] = 2;
                for (int i = 1; i < n - 1; i++) {
                    if (mask & (1 << i)) {
                        if (smask & (1 << i)) tp[i] = 1;
                        else tp[i] = 2;
                    } else tp[i] = 0;
                }
                for (int i = 1; i < n - 1; i++) {
                    if (tp[i] == 0) continue;
                    for (int j = 0; j < n; j++) {
                        if (tp[j] == 0) cur += e[i][j];
                        else if (tp[i] == 1 && tp[j] == 2 || tp[i] == 2 && j == 0) cur += e[i][j];
                    }
                }
                g[mask] = min(g[mask], cur);
                if (smask == 0) break;
            }
        }*/
        /*vector<int> o(1 << n);
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) if (mask & (1 << i)) {
                    for (int j = i + 1; j < n; j++) if (mask & (1 << j)) {
                            o[mask] += e[i][j];
                        }
                }
        }*/

        int ans = INF;
        vector<vector<int> > dp(1 << n, vector<int>(n, INF));
        dp[1][0] = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int last = 0; last < n; last++) {
                if (!(mask & (1 << last))) continue;
                if (dp[mask][last] == INF) continue;
                if (last == n - 1) {
                    //ans = min(ans, dp[mask][last] + g[((1 << n) - 1) ^ mask]);
                    /*if (ans == 49211) {
                        cerr << mask << " " << ((1 << n) - 1) << " " << (((1 << n) - 1) ^ mask) << endl;
                        return 0;
                    }*/
                    //continue;
                }
                vector<int> cost(n);
                for (int nw = 0; nw < n; nw++) {
                    for (int i = 0; i < n; i++) if ((mask & (1 << i)) && i != last) cost[nw] += e[nw][i];
                }
                int rmask = ((1 << n) - 1) ^ mask;
                rmask ^= 1 << (n - 1);
                for (int x = rmask; x; x = (x - 1) & rmask) {
                    int cur = 0;
                    for (int i = 0; i < n; i++) if (x & (1 << i)) cur += cost[i];
                    upd(dp[mask | x][last], dp[mask][last] + cur);
                }

                if (last == n - 1) continue;
                for (int nw = 0; nw < n; nw++) {
                    if (mask & (1 << nw)) continue;
                    if (e[last][nw] == 0) continue;
                    int cost = 0;
                    for (int i = 0; i < n; i++) if ((mask & (1 << i)) && i != last) cost += e[nw][i];
                    upd(dp[mask | (1 << nw)][nw], dp[mask][last] + cost);
                }
            }
        }
        ans = dp[(1 << n) - 1][n - 1];
        cout << ans << endl;
    }


#ifdef HOME
    cerr << "time: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

Measured memory_bytes: 5632