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 <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;

struct edge {
        int a, b, cost;
};

bool comp(const edge& e1, const edge& e2) {
        return e1.cost < e2.cost;
}

struct UnionFind {
        int n;
        vector<int> parent;
        vector<int> rank;
        vector<int> num;
        int find(int x) {
                if (parent[x] == x) return  x;
                return parent[x] = find(parent[x]);
        }
        UnionFind(int n_) {
                n = n_;
                parent.resize(n);
                for (int i = 0; i < n; i ++) parent[i] = i;
                rank.assign(n, 0);
                num.assign(n, 1);
        }
        void unite(int x, int y) {
                if ((x = find(x)) != (y = find(y))) {
                        if (rank[x] < rank[y]) {
                                parent[x] = y;
                                num[y] += num[x];
                        } else {
                                parent[y] = x;
                                if (rank[x] == rank[y]) rank[x] ++;
                                num[x] += num[y];
                        }
                        n --;
                }
        }
        bool same(int x, int y) { return find(x) == find(y); }
        int get() { return n; }
        int get(int x) { return num[find(x)]; }
};

int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        vector<edge> es;
        for (int i = 0; i < m; i ++) {
                int a, b, c;
                scanf("%d%d%d", &a, &b, &c);
                a --, b --;
                es.push_back({a, b, c});
        }
        sort(es.begin(), es.end(), comp);
        UnionFind uf(n);
        int mi = 0;
        vector<int> candidate;
        for (int i = 0; i < es.size(); i ++) {
                edge e = es[i];
                if (!uf.same(e.a, e.b)) {
                        uf.unite(e.a, e.b);
                        mi += e.cost;
                        candidate.push_back(i);
                }
        }
        int ans = 0, sum = 0;
        for (int i = 0; i < candidate.size(); i ++) {
                UnionFind uf2(n);
                int mi2 = 0;
                for (int j = 0; j < es.size(); j ++) {
                        if (candidate[i] == j) continue;
                        edge e = es[j];
                        if (!uf2.same(e.a, e.b)) {
                                uf2.unite(e.a, e.b);
                                mi2 += e.cost;
                        }
                }
                if (mi != mi2) {
                        ans ++;
                        sum += es[candidate[i]].cost;
                }
        }
        printf("%d %d\n", ans, sum);
        return 0;
}