省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現(xiàn)公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可）?，F(xiàn)得到城鎮(zhèn)道路統(tǒng)計表，表中列出了任意兩城鎮(zhèn)間修建道路的費用，以及該道路是否已經(jīng)修通的狀態(tài)?，F(xiàn)請你編寫程序，計算出全省暢通需要的最低成本。

測試輸入包含若干測試用例。每個測試用例的第1行給出村莊數(shù)目N ( 1< N < 100 )；隨后的 N(N-1)/2 行對應(yīng)村莊間道路的成本及修建狀態(tài)，每行給4個正整數(shù)，分別是兩個村莊的編號（從1編號到N），此兩村莊間道路的成本，以及修建狀態(tài)：1表示已建，0表示未建。

當N為0時輸入結(jié)束。

每個測試用例的輸出占一行，輸出全省暢通需要的最低成本。

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

3
0