#3080. Minimum Variance Spanning Tree

题目描述

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

.jpg)

输入格式

多组测试数据。第一行为N,M，依次是点数和边数。接下来M行，每行三个整数U,V,W，代表连接U,V的边，和权值W。保证图连通。(1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50)

输出格式

输出最小方差，四舍五入到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  

数据范围与提示