Spider.java

import java.util.*;
import java.io.*;
 
class Spider {
 
	//private static final boolean DEBUG = true;
 
	public static void main( String[] args ) throws Exception {
		final BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		String line = br.readLine();
		String[] p;
		while ( line != null ) {
			p = line.split( " " );
			int n = toi( p[0] );
			int m = toi( p[1] );
			Edge[] es = new Edge[m];
			int[] v2c = new int[n];
			LinkedList<Integer>[] c2v = new LinkedList[n];
			int c = n; // components count
			for ( int i = 0; i < n; ++i ) { v2c[i] = i; c2v[i] = new LinkedList<Integer>(); c2v[i].add(i); }
 
			for ( int i = 0; i < m; ++i ) {
				p = br.readLine().split(" ");
				es[i] = new Edge( toi(p[0]) - 1, toi(p[1]) - 1, toi(p[2]) );
			}
 
			Arrays.sort( es ); // sort by len
 
			Edge last = es[es.length-1];
			long sum = -last.len;
			int fc, tc;
			fc = v2c[last.from]; // from component
			tc = v2c[last.to]; // to component
			for ( Integer v : c2v[tc] ) {
				v2c[v] = fc;
				c2v[fc].add( v );
			}
			c2v[tc] = null;
			--c;
 
			for ( int i = 0; i < m; ++i ) {
				fc = v2c[es[i].from]; // from component
				tc = v2c[es[i].to]; // to component
				if ( fc == tc ) continue; // already connected
				//if (DEBUG) System.out.println( String.format( "DEBUG: joining %d %d", fc, tc ) );
 
				sum += es[i].len;
				// join components
				for ( Integer v : c2v[tc] ) {
					v2c[v] = fc;
					c2v[fc].add( v );
				}
				c2v[tc] = null;
				--c;
			}
 
			if ( c > 1 ) System.out.println( "disconnected" );
			else System.out.println( sum );
 
			line = br.readLine();
		}
	}
 
	static class Edge implements Comparable<Edge> {
		int from; int to; long len;
 
		Edge( int f, int t, int l ) { from = f; to = t; len = l; }
 
		public int compareTo( Edge e ) {
			if ( this.len == e.len ) return 0;
			return this.len < e.len ? -1 : 1;
		}
 
	}
 
	private static final int toi( String s ) { return Integer.parseInt(s); } 
 
}