Devinez quoi ? En l'an 6202, le serveur de Little Cyan Fish accueille son $10^6$-ième membre ! Vous n'en avez jamais entendu parler ? Eh bien, ce serveur, également connu sous le nom de groupe de Qingyu, est l'endroit où ses amis se retrouvent pour discuter de programmation compétitive, de sujets hors programmation compétitive, de blagues sur PKU, de la gastronomie à Pékin et d'à peu près tout le reste. Mais surtout, le chat regorge chaque jour de messages sur qui est l'idole de qui.
Fidèle à la tradition, Little Cyan Fish organise une fête des idoles avec $n$ membres, numérotés de $1$ à $n$. Il existe $m$ relations fan–idole parmi ces membres : dans la $i$-ième relation, le membre $u_i$ est un fan du membre $v_i$, et un cadeau de $u_i$ à $v_i$ coûte $w_i$. Lors de la fête, chaque membre doit offrir exactement un cadeau spécial à l'une de ses idoles. Cependant, il serait gênant que deux membres s'offrent mutuellement un cadeau (même si cela semble plutôt mignon :p), si bien qu'aucune paire de membres ne peut s'échanger de cadeaux.
Trouvez le coût total minimal des cadeaux, ou déterminez qu'aucune répartition valide n'existe.
Entrée
La première ligne contient un entier $T$ ($1 \le T$), le nombre de cas de test. La description des cas de test suit.
La première ligne de chaque cas de test contient deux entiers $n$ et $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$), représentant respectivement le nombre de membres et le nombre de relations fan–idole.
La $i$-ième des $m$ lignes suivantes contient trois entiers $u_i$, $v_i$ et $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le w_i \le 10^9$), indiquant que le membre $u_i$ est un fan du membre $v_i$ et qu'un cadeau de $u_i$ à $v_i$ coûte $w_i$.
Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $10^6$, et que la somme de $m$ sur l'ensemble des cas de test ne dépasse pas $10^6$. Il est garanti que chaque couple $(u_i, v_i)$ apparaît au plus une fois dans un cas de test. Deux membres peuvent être fans l'un de l'autre.
Sortie
Pour chaque cas de test, affichez un entier — le coût total minimal possible des cadeaux. S'il n'y a pas de solution, affichez $-1$. Affichez chaque réponse sur une ligne séparée.
Exemples
Entrée 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
Sortie 1
6 -1 1
Remarque
Dans le premier cas de test de l'exemple, le membre $1$ offre un cadeau au membre $2$, le membre $2$ au membre $3$, et le membre $3$ au membre $1$. Le coût total est $1 + 2 + 3 = 6$.
Dans le deuxième cas de test de l'exemple, les membres $1$ et $2$ devraient s'offrir des cadeaux mutuellement, donc aucune répartition valide n'existe.
Dans le troisième cas de test de l'exemple, le membre $1$ offre un cadeau au membre $3$, le membre $2$ au membre $1$, et le membre $3$ au membre $2$. Le coût total est $1$.