using System.Collections.Generic;
public class DisjointSetNode<T> {
private DisjointSetNode<T> _parent;
public T Value { get; private set; }
public DisjointSetNode(T val) {
public DisjointSetNode<T> Find() {
while(!ReferenceEquals(root, root._parent)) {
public bool Union(DisjointSetNode<T> other) {
var root2 = other.Find();
if(root1.size >= root2.size) {
root1.size += root2.size;
root2.size += root1.size;
public class Edge<T> : IComparable<Edge<T>> {
public T From { get; private set; }
public T To { get; private set; }
public int Weight { get; private set; }
public Edge(T from, T to, int weight) {
public int CompareTo(Edge<T> other) {
return Weight.CompareTo(other.Weight);
public static int solve(int A, List<List<int>> B) {
var edges = new List<Edge<int>>();
edges.Add(new Edge<int>(n[0], n[1], n[2]));
var set = new Dictionary<int, DisjointSetNode<int>>();
foreach(var node in edges) {
set[node.From] = new DisjointSetNode<int>(node.From);
set[node.To] = new DisjointSetNode<int>(node.To);
var res = new List<Edge<int>>();
while(res.Count < A - 1) {
var next_edge = edges[edgeIdx++];
var x = set[next_edge.From];
var y = set[next_edge.To];
if(x.Find() != y.Find()) {
public static void Main()
var arr = new List<List<int>>() {
new List<int>() {1, 2, 1},
new List<int>() {2, 3, 2},
new List<int>() {3, 4, 4},
new List<int>() {1, 4, 3},
Console.WriteLine("{0}", Solution.solve(4, arr));