¿Adivina qué? ¡En el año 6202, el servidor de Little Cyan Fish le da la bienvenida a su miembro número $10^6$! ¿Nunca has oído hablar de él? Bueno, el servidor, también conocido como el grupo de Qingyu, es donde sus amigos pasan el rato y hablan de programación competitiva, temas fuera de la programación competitiva, chistes de PKU, comida en Pekín y casi cualquier otra cosa. Pero lo más importante es que todos los días el chat está lleno de mensajes sobre quién es el ídolo de quién.
Siguiendo la tradición, Little Cyan Fish está organizando una fiesta de ídolos con $n$ miembros, numerados del $1$ al $n$. Hay $m$ relaciones fan–ídolo entre estos miembros: en la $i$-ésima relación, el miembro $u_i$ es fan del miembro $v_i$, y un regalo de $u_i$ para $v_i$ cuesta $w_i$. En la fiesta, cada miembro debe dar exactamente un regalo especial a uno de sus ídolos. Sin embargo, que dos miembros intercambien regalos entre sí sería incómodo (aunque suena bastante tierno :p), por lo que ningún par de miembros puede darse regalos mutuamente.
Encuentra el costo total mínimo de los regalos, o determina que no existe ninguna asignación válida.
Entrada
La primera línea contiene un entero $T$ ($1 \le T$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.
La primera línea de cada caso de prueba contiene dos enteros $n$ y $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$), el número de miembros y el número de relaciones fan–ídolo, respectivamente.
La $i$-ésima de las siguientes $m$ líneas contiene tres enteros $u_i$, $v_i$ y $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le w_i \le 10^9$), donde el miembro $u_i$ es fan del miembro $v_i$, y un regalo de $u_i$ para $v_i$ cuesta $w_i$.
Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^6$, y la suma de $m$ en todos los casos de prueba no supera $10^6$. Se garantiza que cada par ordenado $(u_i, v_i)$ aparece como máximo una vez en un mismo caso de prueba. Dos miembros pueden ser fans mutuamente.
Salida
Para cada caso de prueba, imprime un entero: el costo total mínimo posible de los regalos. Si no hay solución, imprime $-1$. Imprime cada respuesta en una línea separada.
Ejemplos
Entrada 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
Salida 1
6 -1 1
Nota
En el primer caso de prueba de ejemplo, el miembro $1$ le da un regalo al miembro $2$, el miembro $2$ al miembro $3$ y el miembro $3$ al miembro $1$. El costo total es $1 + 2 + 3 = 6$.
En el segundo caso de prueba de ejemplo, los miembros $1$ y $2$ tendrían que darse regalos mutuamente, por lo que no existe ninguna asignación válida.
En el tercer caso de prueba de ejemplo, el miembro $1$ le da un regalo al miembro $3$, el miembro $2$ al miembro $1$ y el miembro $3$ al miembro $2$. El costo total es $1$.