Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito es un profesor muy respetado y cada vez que viaja a alguna universidad le piden que imparta una conferencia. Fito conoce de muchos temas y por tanto tiene una gran cantidad de conferencias que puede impartir, pero ciertamente no le gusta repetir dos veces la misma conferencia en el mismo lugar. Para resolver esto Fito quiere definir para cada una de sus conferencias una sustituta. De esta forma si al llegar a un lugar con una conferencia preparada no la quiere dar porque sería una repetición entonces puede ofrecer impartir la sustituta. Por supuesto todos las sustitutas son conferencias que ya él tiene preparadas. Para manejar este tipo de situaciones Fito ha preparado una lista de pares de conferencias. Cada par $(a, b)$ expresa que la conferencia $a$ puede ser sustituida por la conferencia $b$ y viceversa. Para cada par, él conoce también la facilidad con que puede hacer el cambio de una conferencia por otra. El valor de la facilidad es simétrico, es decir no importa si se sustituye $a$ por $b$ o viceversa, el valor es el mismo. Fito decide que quiere hallar la forma de asignar a cada conferencia una sustituta tal que la suma del valor de la facilidad de todas las sustituciones sea máxima. Por razones personales de Fito una conferencia $a$ no puede ser sustituta de una conferencia $b$ y al mismo tiempo la conferencia $b$ ser sustituta de $a$.

La primera línea contiene un entero $T$ ($1 \leq T \leq 30$) indicando la cantidad de casos. Cada caso comienza con dos enteros $N$ y $M$ donde $3 \leq N \leq 10000$ y $3 \leq M \leq 50000$. $N$ es el número de conferencias y $M$ es la cantidad de pares de sustitución. Después siguen $M$ líneas, cada una con tres enteros $a$, $b$ y $v$, donde $1 \leq a \lt b \leq N$ y $|v| \leq 100000$. Esto quiere decir que la conferencia $a$ puede ser sustituida por la conferencia $b$ y viceversa con una facilidad $v$. Cada par $(a, b)$ ocurre una sola vez en la entrada.