1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstring> 5 using namespace std; 6 #define N 101 7 #define M 2001 8 typedef double db; 9 int fa[N],a[M],n,m,minv,maxv,rank[N];10 db ans=999999999999999999999999999999.0;11 bool cmp(const int &a,const int &b){return a>b;}12 struct Edge{int u,v,w;db fw;void Read(){scanf("%d%d%d",&u,&v,&w);}}edges[M];13 bool operator < (const Edge &a,const Edge &b){return a.fw<b.fw;}14 void init()15 {16     for(int i=1;i<=n;i++) fa[i]=i;17     memset(rank,0,sizeof(rank));18 }19 int findroot(int x)20 {21     if(x==fa[x]) return x;22     int rt=findroot(fa[x]);23     fa[x]=rt;24     return rt;25 }26 void Union(const int &U,const int &V)27 {28     if(rank[U]<rank[V]) fa[U]=V;29     else30       {31           fa[V]=U;32           if(rank[U]==rank[V]) ++rank[U];33       }34 }35 double sqr(const double &x){return x*x;}36 void kruscal(const int &sum)37 {38     init(); db BA=(db)sum/(db)(n-1);39     int tot=0,all=0; db f_all=0;40     for(int i=1;i<=m;++i) edges[i].fw=sqr((db)edges[i].w-BA);41     sort(edges+1,edges+m+1);42     for(int i=1;i<=m;++i)43       {44           int f1=findroot(edges[i].u),f2=findroot(edges[i].v);45           if(f1!=f2)46             {47                 Union(f1,f2);48                 all+=edges[i].w;49                 f_all+=edges[i].fw;50                 if((++tot)==n-1) break;51             }52       }53     if(all==sum) ans=min(ans,f_all);54 }55 int main()56 {57     scanf("%d%d",&n,&m);58     for(int i=1;i<=m;++i) {edges[i].Read(); a[i]=edges[i].w;}59     sort(a+1,a+m+1); for(int i=1;i<n;++i) minv+=a[i];60     sort(a+1,a+m+1,cmp); for(int i=1;i<n;++i) maxv+=a[i];61     for(int i=minv;i<=maxv;++i) kruscal(i);62     printf("%.4f\n",sqrt(ans/(db)(n-1)));63     return 0;64 }