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;

using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;

constexpr int INF = 1e9;

struct edge {
    int u, v, cost;
    bool operator<(edge const& e) const {
        return cost < e.cost;
    }
};

using edges = vector<edge>;

class union_find {
public:
    union_find(int n) : par(n, -1) {}

    int root(int x) {
        return par[x] < 0 ? x : par[x] = root(par[x]);
    }

    bool unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) {
            return false;
        }
        if(par[x] < par[y]) {
            par[x] += par[y];
            par[y] = x;
        } else {
            par[y] += par[x];
            par[x] = y;
        }
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }

private:
    vector<int> par;
};

int main() {
    int N, M;
    cin >> N >> M;
    edges es(M);
    for(int i = 0; i < M; ++i) {
        cin >> es[i].u >> es[i].v >> es[i].cost;
        es[i].u--; es[i].v--;
    }
    sort(begin(es), end(es));
    int min_cost = 0;
    edges MST;
    {
        union_find uf(N);
        for(auto& e : es) {
            if(uf.unite(e.v, e.u)) {
                min_cost += e.cost;
                MST.push_back(e);
            }
        }
    }
    int ans = 0, ans_cost = 0;
    for(auto& e : MST) {
        union_find uf(N);
        int t = 0;
        for(auto& e2 : es) {
            if(e.u == e2.u && e.v == e2.v) {
                continue;
            }
            if(uf.unite(e2.u, e2.v)) {
                t += e2.cost;
            }
        }
        if(min_cost < t || uf.size(0) != N) {
            ans++;
            ans_cost += e.cost;
        }
    }
    cout << ans << ' ' << ans_cost << endl;
}