#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int g[15][15], dp[15][600005], qwasd[20];
bool vis[20];
signed main() {
    int n, m, x, y, v, t, rzh, hb;
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));
    memset(dp, 0x3f, sizeof(dp));

    for (int i = 1; i <= m; i++)
        cin >> x >> y >> v, g[x][y] = g[y][x] = min(g[x][y], v);

    qwasd[0] = 1;

    for (int i = 1; i <= 15; i++)
        qwasd[i] = qwasd[i - 1] * 3, dp[1][qwasd[i - 1]] = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j < qwasd[n]; j++)
            if (dp[i][j] < 1e9) {
                t = j;
                rzh = 0;
                hb = 0;

                for (int k = n; k >= 0; k--)
                    (t / qwasd[k] == 1) && (hb = k + 1), rzh += (vis[k] = !!(t / qwasd[k])) * qwasd[k], t %= qwasd[k];

                dp[i + 1][rzh] = min(dp[i][j], dp[i + 1][rzh]);

                if (hb) {
                    for (int k = 1; k <= n; k++)
                        (g[hb][k] < 1e9 && !vis[k - 1]) &&
                        (dp[i][j + 2 * qwasd[k - 1]] = min(dp[i][j] + i * g[hb][k], dp[i][j + 2 * qwasd[k - 1]]));

                    dp[i][j + qwasd[hb - 1]] = min(dp[i][j], dp[i][j + qwasd[hb - 1]]);
                }

                for (int k = n; k >= 0; k--)
                    vis[k] = 0;
            }

    cout << dp[n + 1][(qwasd[n] - 1) / 2];
}