一道不错的状压 dp 题。
注意到本质上打通的路径会构成一棵树，因此实际上总花费就是一个点的层高（根节点层高为 0）乘上其到父亲节点的边的边权。
据此可以考虑一种初步的状压 dp 方式（下文点编号 \(1\sim n\)），设 \(f_{h,S}\) 表示层高为 \(h\)，当前已经选的点集为 \(S\) 时的最小花费，转移时考虑枚举 \(h-1\) 层点集 \(S'\)， \(h\) 层点集 \(S''\)，则转移方程 \(f_{h,S}=\min\{f_{h-1,S/S''}+r_{S'',S'}\times h\}\)，其中 \(S/S''\) 表示 \(S\) 挖去 \(S''\) 后剩下的集合，\(r_{S'',S'}\) 表示 \(S''\) 中的每个点 \(x\) 到 \(S'\) 中任意一个点的最短边长之和（对每个 \(x\) 选出来的边的另一端端点可以不同），复杂度 \(O(n2^{3n})\)，过不去。
然而因为这题要求是求最小花费，因此可以考虑优化一下转移过程：转移时枚举前 \(h-1\) 层点集 \(S'\)，自然 \(h\) 层点集 \(S/S'\)，则转移方程 \(f_{h,S}=\min\{f_{h-1,S'}+r_{S/S',S'}\times h\}\)（我代码实现里面写的是枚举 \(S/S'\)，差别不大）。
这样子看起来似乎多了很多不合法方案，比如说 \(h\) 层可以直接连到 \(h-2\) 层了，层数似乎不对？
但是注意到如果出现这种情况，那么最后答案一定是被放大了的，比如 \(h\) 层的点直接连到 \(h-2\) 层，本来层数是 \(h-1\) 但是我们强制算成了 \(h\)，放大了答案，而原先的正确连接方式 \(h-1\) 层连到 \(h-2\) 层并没有从方案中剔除，所以这个 dp 还是正确的。
这样只需要枚举 \(h\) 和 \(S\) 及其子集，复杂度 \(O(n3^n)\)（用 \(O(3^n)\) 枚举子集的方法）
现在问题变成了如何在复杂度内计算 \(r_{S/S',S'}\)，更一般的就是 \(r_{S_1,S_2},S_1\cap S_2=\varnothing\)，此时我们可以考虑从 \(S_1\) 里面拿个点 \(x\) 出来，则 \(r_{S_1,S_2}=r_{S_1/x,S_2}+b_{x,S_2}\)，其中 \(b_{x,S}\) 表示点 \(x\) 到集合 \(S\) 内所有点连边的边权最小值。我们希望 \(r_{S_1,S_2}\) 最小，因此看起来还要枚举 \(x\) 以保证最小，但是注意到转移式子中 \(S_2\) 是不动的，我们只是从 \(S_1\) 中拿出点 \(x\)，因此无论拿哪个点都是一样的（每个点选择的边都是一样的），因此直接转移即可，选 \(x\) 时为了方便直接选 \(\operatorname{lowbit}(S_1)\) 即可，这块复杂度 \(O(4^n)\)，只需要处理 \(b_{x,S}\)。
至于 \(b_{x,S}\)，可以直接 \(O(n^22^n)\) 处理，当然也可以从 \(S\) 选个点出来，因为 \(x\) 到剩余点选择的边是定的，只是往里面多加入一条边取最小值而已，至于两点之间距离直接邻接矩阵存下就完事了。
然后有几个细节需要注意：
- 初值 \(b_{x,0}=INF\)，因为 \(x\) 到 0 无法连出任何边，剩下的全赋 INF 也行不赋也行（因为剩下的转移用不到自身）。
- 初值 \(r_{0,S}=0\) 其余为 INF，原因是空集向集合 \(S\) 连边最小值显然为 0，这里与 \(S\) 向空集连边不同的点在于，\(S\) 向空集连边但是空集里面没有点，所以连边会失败，默认 INF，但是空集向 \(S\) 连边时因为没有点，所以其实连边已经成功了，边长度为 0。
- 初值 \(f_{0,1<<(x-1)}=0\) 其余为 INF。
- 邻接矩阵初始全 INF。
- 计算 \(r\) 的时候注意一下不要让 \(r\) 超出 INF 范围。
- 建议 INF 为 0x3f3f3f3f（int）/0x3f3f3f3f3f3f3f3f（long long），这样可以保证 \(r\) 转移时不会炸范围。
- \(f\) 转移时看一眼当前的 \(r\) 是否为 INF，不是再转移。实际上 \(r_{S_1,S_2}\) 能为 INF 也只有第二维为 0 或者 \(S_1\) 中有个点没有与 \(S_2\) 内所有点的直接连边。
- 在实际转移 \(r\) 时，不需要考虑 \(S_1,S_2\) 无交条件，首先所有合法的 \(S_1,S_2\) 一定都是从合法状态转移而来（挖去一个点两者不可能有交），其次 \(f\) 转移时由于是枚举子集然后挖掉，因此两者同样无交，所以非法状态就随意了。
Code：
/*
========= Plozia =========
Author:Plozia
Problem:P3959 [NOIP2017 提高组] 宝藏
Date:2022/10/16
========= Plozia =========
*/
#include <bits/stdc++.h>
typedef long long LL;
const int MAXN = 12 + 5, MAXP = (1 << 12) + 5;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m, dis[MAXN][MAXN], Bin[MAXP];
LL f[MAXN][MAXP], r[MAXP][MAXP], b[MAXN][MAXP];
int Read()
{
int sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return sum * fh;
}
LL Min(LL x, LL y) { return (x < y) ? x : y; }
int main()
{
n = Read(), m = Read(); memset(dis, 0x3f, sizeof(dis));
if (n == 1) { puts("0"); return 0; }
for (int i = 0; i <= 12; ++i) Bin[1 << i] = i + 1;
for (int i = 1; i <= m; ++i)
{
int x = Read(), y = Read(), z = Read();
dis[x][y] = dis[y][x] = Min(dis[x][y], z);
}
for (int i = 1; i <= n; ++i)
{
b[i][0] = INF;
for (int j = 1; j < (1 << n); ++j)
{
int k = j & (-j);
b[i][j] = Min(b[i][j ^ k], dis[i][Bin[k]]);
}
}
memset(r, 0x3f, sizeof(r));
for (int i = 0; i < (1 << n); ++i) r[0][i] = 0;
for (int i = 1; i < (1 << n); ++i)
{
for (int j = 0; j < (1 << n); ++j)
{
int k = i & (-i);
r[i][j] = Min(INF, r[i ^ k][j] + b[Bin[k]][j]);
}
}
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n; ++i) f[0][1 << (i - 1)] = 0;
for (int h = 1; h < n; ++h)
{
for (int i = 1; i < (1 << n); ++i)
{
for (int j = i; j; j = (j - 1) & i)
{
if (r[j][i ^ j] != INF) f[h][i] = Min(f[h][i], f[h - 1][i ^ j] + r[j][i ^ j] * h);
}
}
}
LL ans = 0x7f7f7f7f7f7f7f7f;
for (int h = 1; h < n; ++h) ans = Min(ans, f[h][(1 << n) - 1]);
printf("%lld\n", ans); return 0;
}