spider.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
 
/**
 *
 * @author cteam040
 */
import java.util.*;
import java.io.*;
public class spider {
    public static void main(String[] s) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String ln;
        next_case:
        while((ln=br.readLine())!=null)
        {
 
            st = new StringTokenizer(ln);
            int nodes = Integer.parseInt(st.nextToken());
            int nEdges = Integer.parseInt(st.nextToken());
            PriorityQueue<Edge> edges = new PriorityQueue<Edge>();
            Edge longest = new Edge(0,0,-1);
            for(int i=0;i<nEdges;i++)
            {
                ln = br.readLine();
                st = new StringTokenizer(ln);
                int node1 = Integer.parseInt(st.nextToken())-1;
                int node2 = Integer.parseInt(st.nextToken())-1;
                int cena = Integer.parseInt(st.nextToken());
                Edge ne = null;
                if(node1>node2)
                    ne = new Edge(node2,node1,cena);
                else
                    ne = new Edge(node1,node2,cena);
                edges.add(ne);
                if(ne.compareTo(longest)>0)
                    longest = ne;
            }
            int[] components = new int[nodes];
            for(int i=0;i<nodes;i++)
                components[i] = i;
            components[longest.a] = longest.b;
            long cena = -longest.cena;
            for(int pridano=0;pridano<nodes-1 && !edges.isEmpty();)
            {
                Edge cur = edges.poll();
                int ca = findRoot(components, cur.a);
                int cb = findRoot(components, cur.b);
                if(ca==cb)
                    continue;
                pridano++;
                cena += cur.cena;
                components[ca] = cb;
            }
            int someroot = findRoot(components, 0);
            for(int i=1;i<nodes;i++)
            {
                if(findRoot(components, i)!=someroot)
                {
                    System.out.println("disconnected");
                    continue next_case;
                }
            }
            System.out.println(cena);
        }
    }
 
 
    public static int findRoot(int[] comps, final int i)
    {
        int j=i;
        while(comps[j]!=j)
        {
            j = comps[j];
        }
        comps[i] = j;
        return j;
    }
 
    public static class Edge implements Comparable<Edge>
    {
        int a,b,cena;
 
        public Edge(int a, int b, int cena) {
            this.a = a;
            this.b = b;
            this.cena = cena;
        }
 
        public int compareTo(Edge arg0) {
            return cena-arg0.cena;
        }
 
    }
}