Riešenie príkladu C - Mosty od užívateľa Matej Kopernicky

import java.lang.Math.*;
import java.util.*;
import java.io.*;
 
 
public class source {
 
	void solve() throws Exception {
		
		int p = nextInt();
		while (p-->0) {
			int n = nextInt(), m = nextInt();
			
			DS ds = new DS(n);
			
//			ds.merge(0,1);
//			ds.merge(3,4);
//			ds.merge(0,3);
//			debug(ds.par);
			
			Edge[] e = new Edge[m];
			
			for (int i=0; i<m; ++i) {
				int z = nextInt(), k = nextInt(), c = nextInt();
				e[i] = new Edge();
				e[i].w=c; e[i].a=z-1; e[i].b=k-1;
			}
			Arrays.sort(e);
			
			int res = 0;
			for (int i=0; i<e.length; ++i) {
				int pa = ds.getPar(e[i].a);
				int pb = ds.getPar(e[i].b);
				if (pa!=pb) {
					res += e[i].w;
					ds.merge(e[i].a, e[i].b);
				}
			}
			println(res);
		}
		
	}
	
	private class Edge implements Comparable<Edge> {
		int w, a, b;
 
		public int compareTo(Edge arg0) {
			return w-arg0.w;
		}
	}
	
	private class DS {
		int[] par;
//		int[] rank;
		
		public DS(int sz) {
			par = new int[sz];
			for (int i=0; i<sz; ++i) par[i]=i;
//			rank = new int[sz];
		}
		
		int getPar(int idx) {
//			debug(par,idx);
			return (idx==par[idx]) ? idx : (par[idx]=getPar(par[idx]));
		}
		
		void merge(int a, int b) {
			if (getPar(a)!=getPar(b)) par[par[a]] = par[b];
		}
		
		
	}
	
	
	////////////////////////////////////////////////
	//MOJ ROMANTICKY TEMPLATE
	
	void debug(Object...os) {
		System.err.println(Arrays.deepToString(os));
	}
	void print(Object...os) {
		if (os!=null && os.length>0) System.out.print(os[0].toString());
		for (int i=1; i<os.length; ++i) System.out.print(" " + os[i].toString());
	}
	void println(Object...os) {
		print(os);
		System.out.println();
	}
	
	BufferedInputStream bis = new BufferedInputStream(System.in);
	String nextWord() throws Exception {
		char c = (char)bis.read();
		while (c<=' ')  c=(char)bis.read();
		StringBuilder sb = new StringBuilder();
		while (c>' ') {
			sb.append(c);
			c=(char)bis.read();
		}
		return new String(sb);
	}
	String nextLine() throws Exception {
		char c = (char)bis.read();
		while (c<=' ')  c=(char)bis.read();
		StringBuilder sb = new StringBuilder();
		while (c!='\n' && c!='\r') {
			sb.append(c);
			c=(char)bis.read();
		}
		return new String(sb);
	}
	int nextInt() throws Exception {
		return Integer.parseInt(nextWord());
	}
	
	public static void main(String[] args) throws Exception {
		new source().solve();
	}
 
}
 

Zvýrazňovanie syntaxe zabezpečil: GeSHi.