记录下每个点的深度，在计算路径权值时更新。

那在确定根节点的情况下，每一条边都会在深度小的时候和深度大的时候都计算。

#include<bits/stdc++.h>
using namespace std;
const int M=1e3+5;
int ans,n,m,minn=1e9,lj[100],dis[100],inf;
bool vis[100];
long long head[M],nxt[M],to[M],w[M],cnt=0;
void jb(int a,int b,int c){
	nxt[++cnt]=head[a];
	head[a]=cnt;
	to[cnt]=b;
	w[cnt]=c;
}
void prim(int x){
	ans=0;
	memset(vis,0,sizeof(vis));
	memset(lj,0,sizeof(lj));
	memset(dis,127,sizeof(dis));
	inf=dis[0];
	dis[x]=0;lj[x]=1;
	int m,k;
	for(int l=1;l<=n;l++){
		m=inf;
		for(int j=1;j<=n;j++)
			if(lj[j]!=0&&(lj[j]-1)*dis[j]<m&&!vis[j])	m=dis[j],k=j;
		vis[k]=1;
		ans+=dis[k]*(lj[k]-1);
		for(int i=head[k];i;i=nxt[i]){
			int v=to[i];
			if(dis[v]>lj[k]*w[i]){
				if(lj[v]!=0) lj[v]=min(lj[v],lj[k]+1);
				else lj[v]=lj[k]+1;
				dis[v]=lj[k]*w[i];
			}
		}
	}
	minn=min(minn,ans);
}
int main(){
//	freopen("treasure.in","r",stdin);
//	freopen("treasure.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		jb(a,b,c);
		jb(b,a,c);
	}
	for(int i=1;i<=n;i++){
		prim(i);
	}
	cout<<minn<<endl;
	return 0;
}