Erroneous Solution to Oil Business

#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;

class DisjointSets {
    private:
        vector<int> parents;
        vector<int> sizes;
    public:
        DisjointSets(int size) : parents(size), sizes(size, 1) {
            for (int i = 0; i < size; i++) {
                parents[i] = i;
            }
        }

        int get_ultimate(int n) {
            return parents[n] == n ? n : (parents[n] = get_ultimate(parents[n]));
        }

        bool link(int n1, int n2) {
            n1 = get_ultimate(n1);
            n2 = get_ultimate(n2);
            if (n1 == n2) {
                return false;
            }
            if (sizes[n1] < sizes[n2]) {
                std::swap(n1, n2);
            }
            sizes[n1] += sizes[n2];
            parents[n2] = n1;
            return true;
        }
};

struct Road {
    int ind;
    int a, b;
    int cost;
};

/**
 * https://codeforces.com/edu/course/2/lesson/7/2/practice/contest/289391/problem/H
 * (sample input omitted due to length)
 */
int main() {
    int city_num;
    int road_num;
    long long total_cost;
    std::cin >> city_num >> road_num >> total_cost;
    vector<Road> roads(road_num);
    for (int i = 0; i < road_num; i++) {
        Road& r = roads[i];
        r.ind = i + 1;  // stupid 1-indexing
        std::cin >> r.a >> r.b >> r.cost;
        r.a--;
        r.b--;
    }

    /*
     * new problem:
     * min # of edges so that the graph's connected and
     * the edge cost >= total_cost
     */
    std::sort(
        roads.begin(), roads.end(),
        [&] (const Road& r1, const Road& r2) { return r1.cost < r2.cost; }
    );
    DisjointSets spanning_tree(city_num);
    int added = 0;
    vector<bool> added_roads(road_num);
    long long cost = 0;
    for (int i = road_num - 1; i >= 0; i--) {
        const Road& r = roads[i];
        bool res = spanning_tree.link(r.a, r.b);
        added_roads[i] = res;
        added += res;
        cost += res * r.cost;
        if (added == road_num - 1) {
            break;
        }
    }

    for (int r = road_num - 1; r >= 0; r--) {
        if (cost >= total_cost) {
            break;
        }
        if (!added_roads[r]) {
            added_roads[r] = true;
            cost += roads[r].cost;
            added++;
        }
    }

    cout << road_num - added << endl;
    for (int r = 0; r < road_num; r++) {
        if (!added_roads[r]) {
            cout << roads[r].ind << ' ';
        }
    }
    cout << endl;
}