Gissa vad? År 6202 välkomnar Little Cyan Fishs server sin $10^6$-te medlem! Har du aldrig hört talas om den? Jo, servern, även känd som Qingyus grupp, är platsen där hans vänner hänger och pratar om tävlingsprogrammering, allt utom tävlingsprogrammering, PKU-skämt, mat i Peking och nästan allt annat. Men viktigast av allt är att chatten varje dag är full av meddelanden om vem som är vems idol.

Enligt traditionen anordnar Little Cyan Fish en idolfest med $n$ medlemmar, numrerade från $1$ till $n$. Det finns $m$ fan–idol-relationer mellan dessa medlemmar: i den $i$-te relationen är medlem $u_i$ ett fan av medlem $v_i$, och en gåva från $u_i$ till $v_i$ kostar $w_i$. På festen måste varje medlem ge exakt en speciell gåva till en av sina idoler. Det skulle dock bli stelt om två medlemmar bytte gåvor med varandra (även om det låter ganska gulligt :p), så inget par av medlemmar får ge gåvor till varandra.

Hitta den minsta totala kostnaden för gåvorna, eller avgör att ingen giltig fördelning existerar.

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T$), antalet testfall. Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller två heltal $n$ och $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$), antalet medlemmar respektive antalet fan–idol-relationer.

Den $i$-te av de följande $m$ raderna innehåller tre heltal $u_i$, $v_i$ och $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le w_i \le 10^9$), där medlem $u_i$ är ett fan av medlem $v_i$, och en gåva från $u_i$ till $v_i$ kostar $w_i$.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^6$, och att summan av $m$ över alla testfall inte överstiger $10^6$. Det garanteras att varje ordnat par $(u_i, v_i)$ förekommer högst en gång i ett testfall. Två medlemmar kan vara fans av varandra.

Utdata

För varje testfall, skriv ut ett heltal — den minsta möjliga totala kostnaden för gåvorna. Om det inte finns någon lösning, skriv ut $-1$. Skriv ut varje svar på en egen rad.

Exempel

Indata 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

Utdata 1

6
-1
1

Förklaring

I det första testfallet i exemplet ger medlem $1$ en gåva till medlem $2$, medlem $2$ till medlem $3$, och medlem $3$ till medlem $1$. Den totala kostnaden är $1 + 2 + 3 = 6$.

I det andra testfallet i exemplet skulle medlemmarna $1$ och $2$ behöva ge gåvor till varandra, så ingen giltig fördelning existerar.

I det tredje testfallet i exemplet ger medlem $1$ en gåva till medlem $3$, medlem $2$ till medlem $1$, och medlem $3$ till medlem $2$. Den totala kostnaden är $1$.