Zgadnijcie co! W roku 6202 serwer Little Cyan Fisha wita swojego $10^6$-tego członka! Nigdy o nim nie słyszeliście? Cóż, ten serwer, znany również jako grupa Qingyu, to miejsce, w którym jego znajomi spędzają czas i rozmawiają o programowaniu turniejowym, tematach niezwiązanych z programowaniem turniejowym, żartach o PKU, jedzeniu w Pekinie i właściwie o wszystkim innym. Ale co najważniejsze, czat jest każdego dnia pełen wiadomości o tym, kto jest czyim idolem.

Zgodnie z tradycją Little Cyan Fish organizuje imprezę idoli z udziałem $n$ członków, ponumerowanych od $1$ do $n$. Pomiędzy tymi członkami istnieje $m$ relacji fan–idol: w $i$-tej relacji członek $u_i$ jest fanem członka $v_i$, a prezent od $u_i$ dla $v_i$ kosztuje $w_i$. Na imprezie każdy członek musi wręczyć dokładnie jeden wyjątkowy prezent jednemu ze swoich idoli. Jednak wymiana prezentów nawzajem między dwoma członkami byłaby niezręczna (choć brzmi to całkiem uroczo :p), więc żadna para członków nie może wręczyć prezentów sobie nawzajem.

Znajdź minimalny łączny koszt prezentów lub stwierdź, że żaden poprawny przydział nie istnieje.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych. Następnie podane są opisy przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$), oznaczające odpowiednio liczbę członków oraz liczbę relacji fan–idol.

$i$-ty z kolejnych $m$ wierszy zawiera trzy liczby całkowite $u_i$, $v_i$ oraz $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le w_i \le 10^9$), co oznacza, że członek $u_i$ jest fanem członka $v_i$, a prezent od $u_i$ dla $v_i$ kosztuje $w_i$.

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^6$, a suma $m$ po wszystkich przypadkach testowych nie przekracza $10^6$. Gwarantowane jest, że każda para uporządkowana $(u_i, v_i)$ pojawia się w jednym przypadku testowym co najwyżej raz. Dwaj członkowie mogą być fanami siebie nawzajem.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą — minimalny możliwy łączny koszt prezentów. Jeśli rozwiązanie nie istnieje, wypisz $-1$. Każdą odpowiedź wypisz w osobnym wierszu.

Przykład

Wejście 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

Wyjście 1

6
-1
1

Uwagi

W pierwszym przykładowym przypadku testowym członek $1$ daje prezent członkowi $2$, członek $2$ członkowi $3$, a członek $3$ członkowi $1$. Łączny koszt wynosi $1 + 2 + 3 = 6$.

W drugim przykładowym przypadku testowym członkowie $1$ i $2$ musieliby dać prezenty sobie nawzajem, więc nie istnieje żaden poprawny przydział.

W trzecim przykładowym przypadku testowym członek $1$ daje prezent członkowi $3$, członek $2$ członkowi $1$, a członek $3$ członkowi $2$. Łączny koszt wynosi $1$.