#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int u, v;
    long long w;
};

struct UnionFind {
    vector<int> parent, rankv;

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

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rankv[rx] < rankv[ry]) parent[rx] = ry;
        else if (rankv[rx] > rankv[ry]) parent[ry] = rx;
        else { parent[ry] = rx; ++rankv[rx]; }
        return true;
    }
};

vector<Edge> kruskal(vector<Edge> &edges, int nodeCount) {
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
        return a.w < b.w;
    });
    UnionFind unionFind(nodeCount);
    vector<Edge> mstEdges;
    for (const auto &e : edges) {
        if (unionFind.unite(e.u, e.v)) {
            mstEdges.push_back(e);
            if ((int)mstEdges.size() == nodeCount - 1) break;
        }
    }
    return {mstEdges};
}