不能通过样例，检查1小时没能查出问题……

/*
dp[h][s]表示前h层树，包含点的集合为s
dp[h][s]=min(dp[h-1][s去掉r]+cost(s去掉r,r)*h)
cost(s^r,r)：r集合中每个点到s^r的最短距离和
*/
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int c[(1<<12)][(1<<12)],cost[(1<<13)][13],d[15][15];
int n,m,u,v,w;
int lowbit(int s){
	return s&(-s);
}
int lg2[(1<<13)],f[15][(1<<13)];
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(d,0x3f,sizeof(d)); //初始化边权极大值 
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		u--; v--; 
		d[u][v]=d[v][u]=w;
	}
	for(int i=0;i<=n;i++){
		lg2[(1<<i)]=i;
	}
	for(int i=0;i<n;i++){
		//c[s][i]:点i到集合s的最短边 
		c[0][i]=1e10;
		for(int s=1;s<(1<<n);s++){
			int k=lowbit(s); //lg2[k]为s集合中最小的元素 
			c[s][i]=min(c[s^k][i],d[lg2[k]][i]); 
			//此处是递推，因为k是最小元素，c[s^k]一定已经处理了 
		}
	} 
	for(int r=1;r<(1<<n);r++){
		//cost[s][r]：r集合每个点到s的最短边之和 
		int k=lowbit(r);
		for(int s=0;s<(1<<n);s++){
			cost[s][r]=cost[s][r^k]+c[s][lg2[k]]; 
		}
	}
	for(int s=0;s<(1<<n);s++){
		f[0][s]=1e10; //赋初值极大值 
	}
	for(int i=0;i<n;i++){
		f[0][(1<<n)]=0; //枚举根 
	}
	for(int h=1;h<n;h++){
		for(int s=1;s<(1<<n);s++){
			f[h][s]=1e10;
			for(int r=s;r!=0;r=(r-1)&s){
				if(cost[s^r][r]==1e10) continue;
				f[h][s]=min(f[h][s],f[h-1][s^r]+cost[s^r][r]*h);
			}
		}
	} 
	int ans=1e10;
	for(int i=0;i<n;i++){
		ans=min(ans,f[i][(1<<n)-1]);
	}
	cout<<ans<<'\n';
	return 0;
}
//感谢.JPG