求最小生成树边之和很简单，难点在求期望。

以任意一个点为祖先节点（为了方便就以编号为1的点好了）给最小生成树确定一个方向。我们如果可以将每条边经过的次数求出来，那么期望＝（每个边经过的次数＊这条边的长度）／总路径数。令总边数为E，总节点数为N，显然总路径数=N*(N-1)/2，而每一个边经过的次数＝以这个点为祖先的子树的节点数＊其它的节点数（注意会爆int）。
    所以我们只需要在最小生成树上用O(N)的时间便利一边就可以求出每个点的子树的节点数。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
int n,m,tol,head[maxn],vis[maxn],fa[maxn];
ll num=0;
double ans=0;
struct node{
    int to,next;
    ll cost;
}edge[maxn];
struct rode{
    int u,v;
    ll w;
}side[maxn];
void add(int u,int v,ll w)
{
    edge[tol].to=v;
    edge[tol].cost=w;
    edge[tol].next=head[u];
    head[u]=tol++;
}
bool cmp(rode a,rode b)
{
    return a.w<b.w;
}
int find(int a)
{
    if(fa[a]==a)
    return a;
    else 
    return fa[a]=find(fa[a]);
}
void lianjie(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a!=b)
    {
        fa[a]=b;
    }
}
ll Krusal( )
{
    int res=0,cnt=0;
    for(int i=1;i<=m;i++)
    {
        int u=side[i].u,v=side[i].v;
        ll w=side[i].w;
        if(find(u)!=find(v))
        {
            lianjie(u,v);
            add(u,v,w);add(v,u,w);
            cnt++;
            res+=w;
        }
    }
    return res;
}
ll dfs(int u,ll wei)
{
    vis[u]=1;
    ll sum=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {   node e=edge[i];
        if(!vis[e.to])
        {
            vis[e.to]=1;
            ll s=dfs(e.to,e.cost);
            sum+=s; 
        }
    }
    num+=sum*(n-sum)*wei;
    return sum;

}
int main()
{   //ios::sync_with_stdio(false);
    ll t;
    scanf("%d",&t);
    while(t--)
    {
       scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        tol=0,num=0;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=m;i++)
        {
            int u,v;
            ll w;
           scanf("%d%d%lld",&u,&v,&w);
            side[i]={u,v,w};
        }
        sort(side+1,side+1+m,cmp);
        ll t=Krusal();
        ll p=dfs(1,0);
        double ans=num*1.0/((n*(n-1)/2));
       printf("%d %.2f\n",t,ans);
    }

}