设$f_{d, s}$表示当前树的深度为$d$，与第一个打通的点连通的点集为$s$。
每次转移的时候不考虑实际的深度，深度都当做$d$，寻找连接两个点集最小边集，如果能连接更浅的点，那么会在之前转移，所以即使转移非法也不可能成为最优解。
找连接两个点集的最小边集合可以预处理。
我比较懒，不想预处理，时间复杂度$O(n^{2}3^{n})$。
Code
/**
* uoj
* Problem#333
* Accepted
* Time: 123ms
* Memory: 1412k
*/
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef bool boolean; const int N = , S = << N;
const signed inf = (signed) (~0u >> ); template <typename T>
void pfill(T* pst, const T* ped, T val) {
for ( ; pst != ped; *(pst++) = val);
} int n, m;
int g[N][N];
int f[N + ][S];
int cost[S]; inline void init() {
scanf("%d%d", &n, &m);
for (int i = ; i < n; i++)
for (int j = ; j < n; j++)
g[i][j] = inf;
for (int i = , u, v, w; i < m; i++) {
scanf("%d%d%d", &u, &v, &w), u--, v--;
g[v][u] = g[u][v] = min(g[u][v], w);
}
} int id[S];
inline void solve() {
int S = ( << n);
pfill(f[], f[n + ], inf);
pfill(cost, cost + S, inf);
for (int i = ; i < n; i++)
id[ << i] = i;
for (int i = ; i < n; i++)
f[][ << i] = ;
int ans = f[][S - ];
for (int d = ; d <= n; d++) {
for (int s = , val; s < S; s++) {
if ((val = f[d - ][s]) == inf)
continue;
cost[] = ;
for (int ns = (s + ) | s, cs, w, wc, cur; ns < S; ns = (ns + ) | s) {
cs = (ns ^ s), w = cost[cs ^ (cs & (-cs))], wc = inf;
if (w == inf)
continue;
cur = id[(cs & (-cs))];
for (int i = ; i < n; i++)
if (s & ( << i))
wc = min(wc, g[cur][i]);
if (wc == inf)
continue;
f[d][ns] = min(f[d][ns], val + (w + wc) * (d - ));
cost[cs] = w + wc;
} for (int ns = s; ns < S; ns = (ns + ) | s)
cost[ns ^ s] = inf;
}
ans = min(ans, f[d][S - ]);
}
printf("%d\n", ans);
} int main() {
init();
solve();
return ;
}