問(wèn)題描述

給定帶權(quán)無(wú)向圖，求出一顆方差最小的生成樹(shù)。

輸入格式

輸入多組測(cè)試數(shù)據(jù)。第一行為N,M，依次是點(diǎn)數(shù)和邊數(shù)。接下來(lái)M行，每行三個(gè)整數(shù)U,V,W，代表連接U,V的邊，和權(quán)值W。保證圖連通。n=m=0標(biāo)志著測(cè)試文件的結(jié)束。

輸出格式

對(duì)于每組數(shù)據(jù)，輸出最小方差，四舍五入到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

數(shù)據(jù)規(guī)模與約定

1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50。數(shù)據(jù)不超過(guò)5組。