题目描述

给定带权无向图，求出一颗方差最小的生成树，方差的定义如下：

$$Var_T=\frac{1}{n-1}\sum_{e\in T}(w(e)-\overline{w})^2 $$$$\overline{w}=\frac{1}{n-1}\sum_{e\in T}w(e)$$

输入格式

多组测试数据。第一行为 $n,m$，依次是点数和边数。接下来 $m$ 行，每行三个整数 $u,v,w$，代表连接 $u,v$ 的边，和权值 $w$。保证图连通。

输出格式

输出最小方差，四舍五入到 $0.01$。输出格式按照样例。

$n=m=0$ 标志着测试文件的结束。

4 5
1 2 1
2 3 2
3 4 2
4 1 1
2 4 3
4 6
1 2 1
2 3 2
3 4 3
4 1 1
2 4 3
1 3 3
0 0

Case 1: 0.22
Case 2: 0.00

数据规模与约定

对于 $100\%$ 的数据，$1\le u,v\le n\le 50$，$n-1\le m\le 10^3$，$0\le w\le 50$。