Gjett hva? I året 6202 ønsker serveren til Little Cyan Fish sitt $10^6$-te medlem velkommen! Aldri hørt om den? Vel, serveren, også kjent som Qingyus gruppe, er stedet der vennene hans henger og snakker om konkurranseprogrammering, alt annet enn konkurranseprogrammering, PKU-vitser, mat i Beijing og nesten alt mulig annet. Men viktigst av alt er chatten hver dag full av meldinger om hvem som er hvem sitt idol.

I tråd med tradisjonen arrangerer Little Cyan Fish en idolfest med $n$ medlemmer, nummerert fra $1$ til $n$. Det er $m$ fan–idol-relasjoner blant disse medlemmene: i den $i$-te relasjonen er medlem $u_i$ en fan av medlem $v_i$, og en gave fra $u_i$ til $v_i$ koster $w_i$. På festen må hvert medlem gi nøyaktig én spesiell gave til ett av sine idoler. Det ville imidlertid vært kleint om to medlemmer utvekslet gaver med hverandre (selv om det høres ganske søtt ut :p), så ingen par av medlemmer kan gi gaver til hverandre.

Finn den minste totale kostnaden for gavene, eller avgjør at ingen gyldig ordning eksisterer.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder to heltall $n$ og $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$), henholdsvis antallet medlemmer og antallet fan–idol-relasjoner.

Den $i$-te av de neste $m$ linjene inneholder tre heltall $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$), der medlem $u_i$ er en fan av medlem $v_i$, og en gave fra $u_i$ til $v_i$ koster $w_i$.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $10^6$, og at summen av $m$ over alle testtilfeller ikke overstiger $10^6$. Det garanteres at hvert ordnede par $(u_i, v_i)$ forekommer høyst én gang i et testtilfelle. To medlemmer kan være fans av hverandre.

Utdata

For hvert testtilfelle, skriv ut et heltall — den minste mulige totale kostnaden for gavene. Hvis det ikke finnes noen løsning, skriv ut $-1$. Skriv ut hvert svar på en egen linje.

Eksempler

Inndata 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

Forklaring

I det første testtilfellet i eksempelet gir medlem $1$ en gave til medlem $2$, medlem $2$ til medlem $3$, og medlem $3$ til medlem $1$. Den totale kostnaden er $1 + 2 + 3 = 6$.

I det andre testtilfellet i eksempelet måtte medlemmene $1$ og $2$ ha gitt gaver til hverandre, så ingen gyldig ordning eksisterer.

I det tredje testtilfellet i eksempelet gir medlem $1$ en gave til medlem $3$, medlem $2$ til medlem $1$, og medlem $3$ til medlem $2$. Den totale kostnaden er $1$.