0 Judge
Code: 0
Lacy 蛙最近接到一個計劃是要幫家鄉做路網規劃 (畢竟他是家鄉唯一上過大學的青蛙), 因為以前他們都是用跳的所以不需要馬(蛙)路, 所以目前是一條馬(蛙)路都沒有的, 要規劃路網是為了發展觀光業。 已經知道 Lacy 的家鄉有 n 個景點, Lacy 的家鄉有 m 個鄉親, 每個鄉親都提議要蓋一座橋連接景點 u 與景點 v 且寬度是 w, 鄉親們不太在意橋的長度只在意橋的寬度, 所以建造一座寬度為 w 的橋的成本是 w 荷葉。也因為不太在意長度的關係, Lacy 提議如果從 u 到 v 可以透過其他寬度大於等於 w 的橋間接到達就可以不用蓋本來想蓋的這座橋來減少成本
聰明的 Lacy 發現，這不就是最大生成樹問題嗎，可是他演算法課睡著了QQ
給每個鄉親的要求, Lacy 請你幫忙他算出最少要多少成本可以滿足所有鄉親的需求
輸入的第一行包含一個整數 $T(T\leq 40)$，代表接下來有 $T$ 個任務。每個任務的第1行是 $n,m(1 \leq n,m \leq 100000$, 接著有 m 行 $u,v,w (1 \leq u \neq v \leq n, 1 \leq w \leq 10^8 )$ 表示每個鄉親的需求
對於每個輸出一行, 表示要滿足每個鄉親的需求最少需要多少成本
所有 $w=1$
$n \leq 1000$
無額外限制