Weißt du was? Im Jahr 6202 heißt der Server von Little Cyan Fish sein $10^6$-tes Mitglied willkommen! Noch nie davon gehört? Nun, der Server, auch bekannt als Qingyus Gruppe, ist der Ort, an dem seine Freunde abhängen und über Competitive Programming, Nicht-Competitive-Programming, PKU-Witze, Essen in Peking und so ziemlich alles andere plaudern. Aber am wichtigsten ist, dass der Chat jeden Tag voller Nachrichten darüber ist, wer wessen Idol ist.
Der Tradition folgend organisiert Little Cyan Fish eine Idol-Party mit $n$ Mitgliedern, die von $1$ bis $n$ nummeriert sind. Es gibt $m$ Fan-Idol-Beziehungen zwischen diesen Mitgliedern: In der $i$-ten Beziehung ist Mitglied $u_i$ ein Fan von Mitglied $v_i$, und ein Geschenk von $u_i$ an $v_i$ kostet $w_i$. Auf der Party muss jedes Mitglied genau ein besonderes Geschenk an eines seiner Idole überreichen. Wenn sich jedoch zwei Mitglieder gegenseitig beschenken würden, wäre das unangenehm (obwohl das ziemlich süß klingt :p), sodass kein Paar von Mitgliedern sich gegenseitig Geschenke machen darf.
Finde die minimalen Gesamtkosten der Geschenke oder stelle fest, dass keine gültige Zuordnung existiert.
Eingabe
Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.
Die erste Zeile jedes Testfalls enthält zwei ganze Zahlen $n$ und $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$), die Anzahl der Mitglieder bzw. die Anzahl der Fan-Idol-Beziehungen.
Die $i$-te der nächsten $m$ Zeilen enthält drei ganze Zahlen $u_i$, $v_i$ und $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le w_i \le 10^9$), wobei Mitglied $u_i$ ein Fan von Mitglied $v_i$ ist und ein Geschenk von $u_i$ an $v_i$ genau $w_i$ kostet.
Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^6$ nicht überschreitet und die Summe von $m$ über alle Testfälle $10^6$ nicht überschreitet. Es wird garantiert, dass jedes geordnete Paar $(u_i, v_i)$ in einem Testfall höchstens einmal vorkommt. Zwei Mitglieder können gegenseitig Fans voneinander sein.
Ausgabe
Gib für jeden Testfall eine ganze Zahl aus — die minimal möglichen Gesamtkosten der Geschenke. Falls es keine Lösung gibt, gib $-1$ aus. Gib jede Antwort in einer eigenen Zeile aus.
Beispiele
Eingabe 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
Ausgabe 1
6 -1 1
Hinweis
Im ersten Beispieltestfall macht Mitglied $1$ ein Geschenk an Mitglied $2$, Mitglied $2$ an Mitglied $3$ und Mitglied $3$ an Mitglied $1$. Die Gesamtkosten betragen $1 + 2 + 3 = 6$.
Im zweiten Beispieltestfall müssten sich die Mitglieder $1$ und $2$ gegenseitig Geschenke machen, weshalb keine gültige Zuordnung existiert.
Im dritten Beispieltestfall macht Mitglied $1$ ein Geschenk an Mitglied $3$, Mitglied $2$ an Mitglied $1$ und Mitglied $3$ an Mitglied $2$. Die Gesamtkosten betragen $1$.