Estradas Escuras.java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static class Aresta implements Comparable<Aresta> {
        int fonte, destino, peso;

        @Override
        public int compareTo(Aresta o) {
            return (this.peso - o.peso);
        }
    };
    
    static int find(int x, int[] pais){
        if (pais[x] != x) {
            pais[x] = find(pais[x], pais);
        }
        return pais[x];
    }

    public static void main(String[] args){
        int m, n;
        int i;

        Scanner scanner = new Scanner(System.in);
        while(true){
            args = scanner.nextLine().split(" ");
            m = Integer.parseInt(args[0]);
            n = Integer.parseInt(args[1]);

            if(m == 0 && n == 0) break;
            i = 0;
            long custo = 0;
            Aresta[] arestas = new Aresta[n];
            int[] pais = new int[m];
            while(i < n){
                args = scanner.nextLine().split(" ");
                arestas[i] = new Aresta();
                arestas[i].fonte = Integer.parseInt(args[0]);
                arestas[i].destino = Integer.parseInt(args[1]);
                arestas[i].peso = Integer.parseInt(args[2]);
                custo += arestas[i].peso;
                i++;
            }
            for (m--; m >= 0; m--){
                pais[m] = m;
            }
            Arrays.sort(arestas);
            for (i = 0; i < n; ++i){//UNIÃO
                Aresta aresta = arestas[i];
                int paiFonte, paiDestino;
                paiFonte = find(aresta.fonte, pais);
                paiDestino = find(aresta.destino, pais);
                if (paiFonte != paiDestino) {
                    custo -= aresta.peso;
                    if (paiFonte > paiDestino){
                        pais[paiFonte] = paiDestino;
                    } else {
                        pais[paiDestino] = paiFonte;
                    }
                }
            }
            System.out.println(custo);
        }
        scanner.close();
    }
}