某省調(diào)查鄉(xiāng)村交通狀況，得到的統(tǒng)計(jì)表中列出了任意兩村莊間的距離。省政府“暢通工程”的目標(biāo)是使全省任何兩個村莊間都可以實(shí)現(xiàn)公路交通（但不一定有直接的公路相連，只要能間接通過公路可達(dá)即可），并要求鋪設(shè)的公路總長度為最小。請計(jì)算最小的公路總長度。

        測試輸入包含若干測試用例。每個測試用例的第1行給出村莊數(shù)目N ( < 100 )；隨后的N(N-1)/2行對應(yīng)村莊間的距離，每行給出一對正整數(shù)，分別是兩個村莊的編號，以及此兩村莊間的距離。為簡單起見，村莊從1到N編號。
        當(dāng)N為0時，輸入結(jié)束，該用例不被處理。

        對每個測試用例，在1行里輸出最小的公路總長度。

8
1 2 42
1 3 68
1 4 35
1 5 1
1 6 70
1 7 25
1 8 79
2 3 59
2 4 63
2 5 65
2 6 6
2 7 46
2 8 82
3 4 28
3 5 62
3 6 92
3 7 96
3 8 43
4 5 28
4 6 37
4 7 92
4 8 5
5 6 3
5 7 54
5 8 93
6 7 83
6 8 22
7 8 17
0

82