记录编号	308549	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]生日快乐！小埋!	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	4.632 s
提交时间	2016-09-18 11:13:16	内存使用	0.28 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 105;
const int maxm = 2005;
const int inf = 2e9;


#define is_num(x) (x <= '9' and x >= '0')
inline int get_num() {
	char tmp = getchar();
	int res = 0;
	
	while (not is_num(tmp)) tmp = getchar();
	while (    is_num(tmp)) {
		res = (res << 3) + (res << 1) + tmp - '0';
		tmp = getchar();
	}
	
	return res;
}


struct Edge {
	int fr, to, v;
	double fix;
	Edge() { fr = 0, to = 0, v = 0;}
	Edge(int fr_, int to_, int v_) { fr = fr_, to = to_, v = v_; }
	
	
	bool operator < (const Edge &b) const { 
		return fix < b.fix;
	}
}e[maxm];


int v_mi, v_mx, m, n;


class UnionFindSet {
private:
	int fa[maxn];
public:
	inline void init(int top) {
		for (int i = 1; i <= top; i++) fa[i] = i;
	}
	
	
	inline int get_fa(int now) {
		return fa[now] = fa[now] == now ? now : get_fa(fa[now]);
	}
	
	
	inline void union_set(int u, int v) {
		int fau = get_fa(u), fav = get_fa(v);
		if (fau == fav) return;
		
		fa[fau] = fav;
	}
	
	
	inline bool same(int u, int v) {
		return get_fa(u) == get_fa(v);
	}
}ufs; 


inline double kruskal(double ave) {
	double tot = ave;
	ave /= n - 1;
	for (int i = 1; i <= m; i++) {
		e[i].fix = (ave - e[i].v) * (ave - e[i].v);
	}
	
	sort(e + 1, e + m + 1);
	ufs.init(n);
	double sum = 0;
	double ans = 0;
	int now = 0;
	
	for (int i = 1; i <= m; i++) {
		int u = e[i].fr, v = e[i].to;
		if (ufs.same(u, v)) continue;
		
		sum += e[i].v;
		ans += e[i].fix;
		
		ufs.union_set(u, v);
		if(++now == n - 1) break;
	}
	
	if (tot != sum) return inf;
	return sqrt(ans / (n - 1));
}


inline void read() {
	n = get_num();
	m = get_num();
	int fr, to, v;
	for (int i = 1; i <= m; i++) {
		fr = get_num();
		to = get_num();
		v = get_num();
		e[i] = Edge(fr, to, v);
		e[i].fix = e[i].v;
	}
}


inline void solve() {
	double res = inf;
	
	sort(e + 1, e + m + 1);
	for (int i = 1; i <= n - 1; i++) {
		v_mi += e[i].v;
		v_mx += e[m - i + 1].v;
	}
	
	for (int i = v_mi; i <= v_mx; i++) {
		res = min(res, kruskal(i));
	}
	
	printf("%.4lf\n", res);
}


int main() {
	freopen("happy_birthday.in", "r", stdin);
	freopen("happy_birthday.out", "w", stdout);
	read();
	solve();
	return 0;
}