Problem: Example

Input

4 4
1 2 3
1 3 3
2 3 3
2 4 3


Output

1 3

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
class UnionFindTree {
private:
    vector<int> parent;
    vector<int> count;
public:
    UnionFindTree(int n) : parent(n), count(n, 1) {
        for(int i = 0; i < n; i++) parent[i] = i;
    }
    int get_root(const int x) {
        if (parent[x] == x) return x;
        return parent[x] = get_root(parent[x]);
    }
    void unite(const int x, const int y) {
        int rx = get_root(x), ry = get_root(y);
        if (rx == ry) return;
        parent[rx] = ry;
        count[ry] += count[rx];
        count[rx] = 0;
    }
    bool is_same_root(const int x, const int y) { return get_root(x) == get_root(y); }
    int get_size(const int x) { return count[get_root(x)]; }
    void print() {
        for(auto elm : parent) cout << elm << " ";
        cout << endl;
        for(auto elm : count) cout << elm << " ";
        cout << endl;
    }
};

int main(){
    int n, m; cin >> n >> m;
    vector<pair<int, pair<int, int>>> edge;
    map<int, vector<pair<int, int>>> cost;
    for (auto i = 0; i < m; i++) {
        int s, d, c; cin >> s >> d >> c; s--; d--;
        cost[c].emplace_back(s, d);
    }
    UnionFindTree tree(n); int64_t min_cost = 0;
    for (auto & vec : cost) {
        for (auto & elm : vec.second) {
            if (tree.is_same_root(elm.first, elm.second)) continue;
            tree.unite(elm.first, elm.second);
            edge.emplace_back(vec.first, elm);
            min_cost += vec.first;
        }
    }

    pair<int, int> ans;
    for (auto & a : edge) {
        UnionFindTree tmp(n); int64_t sum = 0;
        for (auto & vec : cost) {
            for (auto & elm : vec.second) {
                if (a.first == vec.first and elm == a.second) continue;
                if (tmp.is_same_root(elm.first, elm.second)) continue;
                tmp.unite(elm.first, elm.second);
                sum += vec.first;
            }
        }
        if(tmp.get_size(0) != n or sum > min_cost) ans.first++, ans.second += a.first;
    }

    cout << ans.first << " " << ans.second << endl;
    return 0;
}