問題描述

給定帶權無向圖，求出一顆方差最小的生成樹。

輸入格式

輸入多組測試數據。第一行為N,M，依次是點數和邊數。接下來M行，每行三個整數U,V,W，代表連接U,V的邊，和權值W。保證圖連通。n=m=0標志著測試文件的結束。

輸出格式

對于每組數據，輸出最小方差，四舍五入到0.01。輸出格式按照樣例。

樣例輸入

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

數據規模與約定

1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50。數據不超過5組。