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 <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

constexpr ll INF = 1LL << 60;

struct Edge {
    int from, to;
    ll cost;
    Edge(int f, int t, ll c): from(f), to(t), cost(c) {}
    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    bool operator==(const Edge &e) const {
        return (from == e.from) && (to == e.to) && (cost == e.cost);
    }
};

class UnionFind {
    public:
    int n;
    vector<int> par, rank, size;  //親, 深さ, その木の要素数

    UnionFind(int n): n(n) {
        for(int i=0;i<n;++i){
            par.push_back(i);
            rank.push_back(0);
            size.push_back(1);
        }
    }

    //根を求める
    int find(int x){
        if(par[x] == x){
            return x;
        }else{
            int p = find(par[x]);
            size[x] = size[p];
            return par[x] = p;
        }
    }

    //xとyの属する集合の併合
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        
        size[x] += size[y];
        size[y] = size[x];
        if(rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }

    //同じ集合に属するか否か
    bool are_same(int x, int y){
        return find(x) == find(y);
    }
};


ll kruskal(int &n, vector<Edge> &edges, vector<Edge> &used_edges, Edge unused_edge) {
    bool is_all = (unused_edge.cost == -1);
    UnionFind uf = UnionFind(n);
    ll cost = 0LL;
    for(Edge e: edges) {
        if(e == unused_edge) continue;
        if(!uf.are_same(e.from, e.to)) {
            uf.unite(e.from, e.to);
            cost += e.cost;
            if(is_all) used_edges.push_back(e);
        }
    }

    int p = uf.find(0);
    for(int i=1;i<n;++i) {
        if(uf.find(i) != p) return INF;
    }

    return cost;
}

int main() {
    int n, m;
    cin >> n >> m;
    int s,d; ll c;
    vector<Edge> edges;
    vector<int> degrees(n, 0);
    for(int i=0;i<m;++i){
        cin >> s >> d >> c;
        --s; --d;
        Edge e = Edge(s, d, c);
        edges.push_back(e);
    }
    sort(edges.begin(), edges.end());

    vector<Edge> used_edges;
    ll min_cost = kruskal(n, edges, used_edges, Edge(-1, -1, -1));

    int ans_cnt = 0;
    ll ans_cost = 0LL;
    for(Edge e: used_edges) {
        if(kruskal(n, edges, used_edges, e) > min_cost) {
            ++ans_cnt;
            ans_cost += e.cost;
        }
    }

    cout << ans_cnt << " " << ans_cost << endl;

}