#include<bits/stdc++.h>
using namespace std;
const int N = 12, M = 1 << 12, INF = 0x3f3f3f3f;

int n, m;
int d[N][N];
int f[M][N], g[M];

int get_cost(int cur, int pre)
{
    //如果pre延申不到cur 
    if((g[pre] & cur) != cur) return -1;
    int remain = pre ^ cur; //待更新的方案
    int cost = 0; //边权之和
    for(int i = 0; i < n; i++)
    {
        if(remain >> i & 1)
        {
            int t = INF; //找到当前连通块内能把该点加入所用的最小边边长
            for(int j = 0; j < n; j++)
                if(pre >> j & 1)
                    t = min(t, d[j][i]);
            
            cost += t;
        }
    }
    return cost;
}

int main()
{
    cin >> n >> m;
    memset(d, 0x3f, sizeof d);
    for(int i = 0; i < n; i++)
        d[i][i] = 0;
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a --, b --;
        d[a][b] = d[b][a] = min(d[a][b], c);
    }
    //预处理所有状态能够扩展一层后得到的最大的下一层
    for(int i = 1; i < 1 << n; i ++)
        for(int j = 0; j < n; j++)
            if(i >> j & 1)
            {
                for(int k = 0; k < n; k++)
                    if(d[j][k] != INF)
                        g[i] |= 1 << k;
            }
    
    memset(f, 0x3f, sizeof f);

    //开局的起点
    for(int i = 0; i < n; i++) f[1 << i][0] = 0;

    for(int cur = 1, cost; cur < 1 << n; cur ++)
        for(int pre = cur - 1 & cur; pre; pre = pre - 1 & cur)
            if(~(cost = get_cost(cur, pre)))
                for(int k = 1; k < n; k++)
                    f[cur][k] = min(f[cur][k], f[pre][k - 1] + cost * k);
    
    int res = INF;
    for(int k = 0; k < n; k ++)
       // cout << f[(1 << n) - 1][k] << endl;
        res = min(res, f[(1 << n) - 1][k]);
    
    cout << res;
    
    return 0;
}

/*
题意： 给定n个点，m条边，连通的无向图
初始：无向图没有边，每个点互不连通，可以选择任意一个点为起点，费用为0

爆搜+优化 -> 记忆化搜索 -> DP

生成树的状态作为DP的状态，且要额外记录树的深度
即我们把起点作为树的root然后一层层构造生成树

f[i][j]:当前生成树的状态是i，且树的深度为j的方案
        属性： Min
计算：f[i][j] = min(f[pre][j - 1] + j * cost)
初始状态: f[i][0]
目标状态：f[1...1][j]

pre：枚举所有树i的子集，cost是由pre扩展一层到达i这个状态时所用的所有边的边权之和

f(0001, 0) -> f(0011, 1) -> f(1111, 2)

时间复杂度分析：
包含k个元素的集合有C(n, k)个，且每个集合有2^k个子集 因此一共有c(n, k)2^k个子集
k [0, n]  在总共有 (1 + 2)^n = 3^n

对于每个子集 n^2次计算剩余点到子集中的最短边
O(n^2*3^n)
*/