Spider.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Spider {
	public static void main(String[] args) throws NumberFormatException, IOException {
 
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
		String s;
		while((s = br.readLine()) != null){
			StringTokenizer st = new StringTokenizer(s);
			List<Edge> list = new LinkedList<Edge>();
			List<Edge> fin = new LinkedList<Edge>();
			int n = Integer.parseInt(st.nextToken());
			int neges = Integer.parseInt(st.nextToken());
			int[] rel = new int[n];
 
			for(int i=0; i<n; i++){
				rel[i] = i;
			}
 
			for(int i = 0; i< neges; i++){
				st = new StringTokenizer( br.readLine() );
				Edge e= new Edge( Integer.parseInt(st.nextToken())-1,
						Integer.parseInt(st.nextToken())-1,
						Integer.parseInt(st.nextToken())
						);
				list.add(e);
			}
 
			PriorityQueue<Edge> pqm = new PriorityQueue<Edge>(list);
 
			while(fin.size() < n-1 && !pqm.isEmpty()){
				Edge min = pqm.remove();
 
				int a = min.a;
				int b = min.b;
 
				while(a != rel[a]){
					a = rel[a];
				}
				while(b != rel[b]){
					b = rel[b];
				}
 
				if(a!=b){					
					fin.add(min);
					rel[b] = rel[a] = Math.min(a, b);
				}
 
			}
 
			int maxEdge = 0;
			for(Iterator<Edge> it = fin.iterator(); it.hasNext(); ){
				Edge ed = it.next();
				if(ed.length>maxEdge){
					maxEdge = ed.length;
				}
			}
 
			int sum=0;
			for(Edge ed: fin){
				sum+= ed.length;
			}
			if (fin.size() == n-1){
				System.out.println(2*maxEdge-sum);
			}
			else 
				System.out.println("disconnected");
 
		}
 
	}
}
 
class Edge implements Comparable<Edge>{
	int a;
	int b;
	int length;
 
	public Edge( int a, int b, int length){
		this.a = a;
		this.b = b;
		this.length = length;
	}
 
	public int compareTo(Edge e){
		return this.length - e.length;
	}
 
	@Override
	public String toString() {
		return "Edge [a=" + a + ", b=" + b + ", length=" + length + "]";
	}
 
 
}