struct Edge {
  int src, dest, weight;
};

struct compare {
  bool operator()(Edge const &a, Edge const &b) const {
    return a.weight > b.weight;
  }
};

class DisjointSet {
  unordered_map<int, int> parent;

public:
  void makeSet(int n) {

    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }
  }

  int Find(int k) {

    if (parent[k] == k) {
      return k;
    }

    return Find(parent[k]);
  }

  void Union(int a, int b) {

    int x = Find(a);
    int y = Find(b);

    parent[x] = y;
  }
};

vector<Edge> runKruskalAlgorithm(vector<Edge> edges, int n) {

  vector<Edge> MST;

  DisjointSet ds;

  ds.makeSet(n);

  sort(edges.begin(), edges.end(), compare());

  while (MST.size() != n - 1) {

    Edge next_edge = edges.back();
    edges.pop_back();

    int x = ds.Find(next_edge.src);
    int y = ds.Find(next_edge.dest);

    if (x != y) {
      MST.push_back(next_edge);
      ds.Union(x, y);
    }
  }
  return MST;
}