C - Mosty

Po rozlúsknutí Einstein-Rosenovho mosta sa objavu okamžite uchopila armáda a plánuje vytvorenie siete obojsmerných mostov, pomocou ktorej by v priebehu minút mohla premiestniť vojakov na ľubovoľnú planétu pod svojou kontrolou a chrániť tak obrovské územie ríše bez nutnosti verbovať hordy občanov.

Keďže je to nová technológia, má značné obmedzenia a ani armádny rozpočet nie je bezodný, stačí, že sa medzi ľubovoľnými planétami dá cestovať, aj za cenu prestupov.
Náročnosť zhotovenia samotného mosta medzi niektorými dvomi planétami navyše okrem vzdialenosti komplikujú okolnosti ako rozdielna gravitácia a prítomnosť čiernej diery niekde na spojnici. Pre isté dvojice planét vedci odhadli cenu za zhotovenie mosta a ostáva už len spočítať, za akú najmenšiu sumu sa dá sieť postaviť (dvojice planét sú vybraté tak, aby sa kompletná sieť dala postaviť vždy)

Vstup

Prvý riadok vstupu obsahuje kladné celé číslo P určujúce počet testovacích sád. Každá sada začína riadkom s dvoma celými číslami N a M, ktoré určujú počet planét a dvojíc, ku ktorým existuje odhad ceny mosta.
Nasledujúcich M riadkov obsahuje tri medzerou oddelené celé čísla z, k a c. Čísla z a k určujú dvojicu planét (číslované od 1) a c cenu za spojenie týchto planét mostom.

1 ≤ P ≤ 50
1 ≤ z, k ≤ N≤200
1 ≤ c ≤ 1000

Výstup

Pre každú testovaciu sadu vypíšte jeden riadok obsahujúci cenu za vytvorenie siete prepojení umožňujúcej cestovanie medzi ľubovoľnými bránami (nie nutne priamo).

Príklad

Vstup:

2
4 4
1 2 2
2 3 1
3 4 2
4 1 4
3 3
1 2 5
2 3 5
1 3 10

Výstup:

5
10