Gettu hvað? Árið 6202 býður netþjónn Little Cyan Fish sinn $10^6$-ta meðlim velkominn! Aldrei heyrt um hann? Jú, netþjónninn, einnig þekktur sem hópur Qingyu, er staðurinn þar sem vinir hans hanga og spjalla um keppnisforritun, annað en keppnisforritun, PKU-brandara, mat í Peking og nánast allt annað. En það mikilvægasta er að spjallið er fullt af skilaboðum á hverjum degi um hver sé átrúnaðargoð hvers.

Samkvæmt hefðinni heldur Little Cyan Fish átrúnaðargoðaveislu með $n$ meðlimum, sem eru númeraðir frá $1$ til $n$. Það eru $m$ aðdáanda–átrúnaðargoðatengsl á milli þessara meðlima: í $i$-ta tengslinu er meðlimur $u_i$ aðdáandi meðlims $v_i$, og gjöf frá $u_i$ til $v_i$ kostar $w_i$. Í veislunni verður hver meðlimur að gefa einmitt eina sérstaka gjöf til eins af átrúnaðargoðum sínum. Hins vegar væri vandræðalegt ef tveir meðlimir myndu skiptast á gjöfum hvor við annan (þótt það hljómi frekar sætt :p), þannig að ekkert par af meðlimum má gefa hvor öðrum gjafir.

Finndu lágmarks heildarkostnað gjafanna, eða skerðu úr um að engin gild skipan sé til.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T$), fjölda prófunartilvika. Lýsingin á prófunartilvikunum fylgir á eftir.

Fyrsta línan í hverju prófunartilviki inniheldur tvær heiltölur $n$ og $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$), fjölda meðlima og fjölda aðdáanda–átrúnaðargoðatengsla, í þeirri röð.

$i$-ta línan af næstu $m$ línum inniheldur þrjár heiltölur $u_i$, $v_i$ og $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le w_i \le 10^9$), þar sem meðlimur $u_i$ er aðdáandi meðlims $v_i$, og gjöf frá $u_i$ til $v_i$ kostar $w_i$.

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^6$, og að summa $m$ yfir öll prófunartilvik fari ekki yfir $10^6$. Það er tryggt að hvert raðað par $(u_i, v_i)$ komi fyrir í mesta lagi einu sinni í prófunartilviki. Tveir meðlimir geta verið aðdáendur hvor annars.

Úttak

Fyrir hvert prófunartilvik skal prenta út heiltölu — minnsta mögulega heildarkostnað gjafanna. Ef engin lausn er til skal prenta út $-1$. Prentið hvert svar á sér línu.

Dæmi

Inntak 1

3
3 3
1 2 1
2 3 2
3 1 3
2 2
1 2 0
2 1 0
3 4
1 2 0
1 3 1
2 1 0
3 2 0

Úttak 1

6
-1
1

Athugasemd

Í fyrsta prófunartilvikinu í dæminu gefur meðlimur $1$ meðlimi $2$ gjöf, meðlimur $2$ gefur meðlimi $3$, og meðlimur $3$ gefur meðlimi $1$. Heildarkostnaðurinn er $1 + 2 + 3 = 6$.

Í öðru prófunartilvikinu í dæminu þyrftu meðlimir $1$ og $2$ að gefa hvor öðrum gjafir, þannig að engin gild skipan er til.

Í þriðja prófunartilvikinu í dæminu gefur meðlimur $1$ meðlimi $3$ gjöf, meðlimur $2$ gefur meðlimi $1$, og meðlimur $3$ gefur meðlimi $2$. Heildarkostnaðurinn er $1$.