Desbloqueando Bloqueos En el país de Code-livia existen muchos bloqueos tantos que a veces no hay camino a los diferentes destinos que este bello país ofrece.
Existen N destinos en el país numerados de 1 al N, algunos están desconectados ya que existen bloqueos en los caminos. Necesitamos que por lo menos haya una ruta entre un destino y otro pero desbloqueando la menor cantidad de rutas bloqueadas. Se garantiza que hay una forma de lograr esto.
En la primera linea le darán un numero entero T (1 ≤ T ≤ 100) el numero de casos de prueba. Por cada caso de prueba le darán una linea con dos enteros N (3 ≤ N ≤ 50), M (N − 1 ≤ M ≤ 500), N es la cantidad de destinos, M la cantidad de conexiones entre ellos.
Las siguientes M lineas contienen tres números X, Y y C (1 ≤ X,Y ≤ N) además X y Y son diferentes). Donde X y Y representan una conexión entre el destino X y el destino Y . C es el estado de la carretera donde 1 significa que la carretera esta desbloqueada y 0 si la carretera esta bloqueada.
Por cada caso de prueba imprima un entero correspondiente a la mínima cantidad de caminos que hay que desbloquear para que todo el país este conectado nuevamente.
2 33 120 230 130 67 121 160 230 250 341 350 560
2 3
#2012