Arvaa mitä? Vuonna 6202 Little Cyan Fishin palvelin toivottaa tervetulleeksi $10^6$. jäsenensä! Etkö ole koskaan kuullut siitä? Palvelin, joka tunnetaan myös Qingyun ryhmänä, on paikka, jossa hänen ystävänsä viettävät aikaa ja juttelevat kilpaohjelmoinnista, muusta kuin kilpaohjelmoinnista, PKU-vitseistä, Pekingin ruoasta ja melkein kaikesta muustakin. Mutta mikä tärkeintä, keskustelu on joka päivä täynnä viestejä siitä, kuka on kenenkin idoli.

Perinteitä kunnioittaen Little Cyan Fish järjestää idolijuhlat, joihin osallistuu $n$ jäsentä, jotka on numeroitu luvuilla väliltä $1$ – $n$. Näiden jäsenten välillä on $m$ fani–idoli-suhdetta: $i$. suhteessa jäsen $u_i$ on jäsenen $v_i$ fani, ja lahja jäseneltä $u_i$ jäsenelle $v_i$ maksaa $w_i$. Juhlissa jokaisen jäsenen täytyy antaa täsmälleen yksi erityinen lahja yhdelle idoleistaan. Kahden jäsenen välinen lahjojen vaihtaminen keskenään olisi kuitenkin kiusallista (vaikka se kuulostaakin aika suloiselta :p), joten mikään jäsenpari ei saa antaa lahjoja toisilleen.

Etsi lahjojen pienin mahdollinen kokonaiskustannus tai päätä, ettei kelvollista järjestelyä ole olemassa.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T$), testitapausten lukumäärän. Seuraavaksi seuraa testitapausten kuvaus.

Jokaisen testitapauksen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$), jäsenten lukumäärän ja fani–idoli-suhteiden lukumäärän tässä järjestyksessä.

Seuraavien $m$ rivin $i$. rivi sisältää kolme kokonaislukua $u_i$, $v_i$ ja $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le w_i \le 10^9$), missä jäsen $u_i$ on jäsenen $v_i$ fani, ja lahja jäseneltä $u_i$ jäsenelle $v_i$ maksaa $w_i$.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten on enintään $10^6$, ja lukujen $m$ summa yli kaikkien testitapausten on enintään $10^6$. On taattu, että jokainen järjestetty pari $(u_i, v_i)$ esiintyy korkeintaan kerran yhdessä testitapauksessa. Kaksi jäsentä voivat olla toistensa faneja.

Tuloste

Tulosta jokaiselle testitapaukselle kokonaisluku — lahjojen pienin mahdollinen kokonaiskustannus. Jos ratkaisua ei ole, tulosta $-1$. Tulosta jokainen vastaus omalle rivilleen.

Esimerkit

Syöte 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

Tuloste 1

6
-1
1

Huomautus

Esimerkin ensimmäisessä testitapauksessa jäsen $1$ antaa lahjan jäsenelle $2$, jäsen $2$ jäsenelle $3$, ja jäsen $3$ jäsenelle $1$. Kokonaiskustannus on $1 + 2 + 3 = 6$.

Esimerkin toisessa testitapauksessa jäsenten $1$ ja $2$ täytyisi antaa lahjat toisilleen, joten kelvollista järjestelyä ei ole olemassa.

Esimerkin kolmannessa testitapauksessa jäsen $1$ antaa lahjan jäsenelle $3$, jäsen $2$ jäsenelle $1$, ja jäsen $3$ jäsenelle $2$. Kokonaiskustannus on $1$.