11631 - Dark roads

Byteland市政府打算實施一項節能減碳計劃，欲關閉部份街道的路燈來達到省電的目的。目前每條街道的路燈都是整夜開著的，每一天，每一公尺的的電費為1塊錢。雖然這個方法可以節省市府開支，但是為了夜間治安上的考量，又必須讓附近的居民覺得生活不受影響，所以他們以下列方法最佳化路燈的開支：關閉部份路燈，並保證從每個交叉路口到任一個路口一定存在一條路徑是路徑上所有街道的燈都是開著的。

請你幫市政府計算一個晚上最多可節省多少電費，而不會使得市民覺得夜間安全受到威脅。

Input Specification

輸入有多筆測試資料，每組資料一開頭會給定兩個整數 m, n(1 <= m <= 200000; m-1 <= n <= 200000)，m表示交叉路口的總數，n表示街道總數，當m=n=0表測試資料結束。接下來的 n 列每列有3個整數x, y ,z分別表示雙向街道由 x 點到 y 點的長度為 z 公尺(0 <= x, y < m 且 x != y)。所有街道的長度總合必小於2^31。

Output Specification

請輸出市政一個晚上可節省多少電費。

Sample Input

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0

Sample Output

51

---

原文出處