在若干年前，某大公司在全國 N 個城市有分公司。 網絡建設在這個國家剛剛開始，所有城市之間的網絡均由同一間網絡供應商提供。 開始時，網絡供應商只提供有限的城市與城市之間的連線，所有連線都是雙向的。 若我們說兩個城市之間有網絡連通，則這兩個城市之間有直接或間接（通過其他一至多個城市）有網絡線連接起來。 在最初時，並不是所有城市之間都有網絡連通，網絡供應商慢慢地完善他的網絡建設。 每對城市之間的連線價錢並不相同，作為某大公司的 CEO，你決定要選擇租用部份網絡連線， 使盡量多的分公司之間都可以連線，並且期總價錢為最低者。
另一方面，每個季度完結之後，網絡供應商會對部份連線的價錢進行調整（價錢可加可減）， 同時亦可能有些新的連線提供。 因此，你每個季度都要重新調整你選擇的連線組合，但目的不變， 即要使盡量多的分公司之間都可以連線，並其總價錢為最低者。
輸入的第一行上有一個正整數 N，它代表城市的數目（每個城市上都有一間分公司）。 其後有若干組數據，每組數據均有以下的格式：
第一行上有一個正整數 C，代表一個季度中新出現的或有價錢調整的連線數目。 隨後有 C 行，每行有三個整數，v u p，其中 u v 為城市的編號（1 至 N, 且 N ≤ 10,000), 它們代表 u v 之間的連線新的價錢為 p。 u v 之間的連線可能是一個新增的連線或舊有的連線。(u < v)
最後一組輸入只有一個 0，代表輸入的結束。
已知任何時候，連線的總數目少於或等於 4N。第一組輸入其實是代表最初時的網絡連線的情況。
對應於每組輸入數據，輸出該某大公司租用網絡的新最少總價錢。 已知在任何時候，總租用費用均少於 109。
4 3 1 2 10 2 3 40 1 3 15 2 2 3 5 2 4 13 0
25 28
在第一組數據中，城市 4 是沒有連線到其他城市。 而在第二組數據中，城市 2 與城市 3 之間的連線減價，同時新增了一條由城市 2 至城市 4 的連線。
#非官方測試數據
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||