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;
typedef pair<int, int> P;
typedef pair<int, P> P3;
typedef pair<P ,P> PP;

struct UnionFindTree {
    vector<int> par;
    vector<int> rank;
    vector<int> siz;

    void init(int n) {
        par.resize(n);
        rank.resize(n);
        siz.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
            siz[i] = 1;
        }
    }
    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) rank[x]++;
        par[y] = x;
        siz[x] += siz[y];
    }
    bool is_same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        x = find(x);
        return siz[x];
    }
};

int n, m;
vector<P3> es;
UnionFindTree uf;
vector<vector<P> > g;
bool noAlt[50005];

// pre->nowの辺が閉路に含まれるか
bool dfs(int now, int pre, int t, int sc){
    if(now == t) return true;
    for(auto e : g[now]){
        int to = e.first, c = es[e.second].first;
        if(to == pre)continue;
        if(dfs(to, now, t, sc)){
            if(c == sc) noAlt[e.second] = false;  // 同じコストは除く
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int s, d, c;
        cin >> s >> d >> c;
        s--; d--;
        es.push_back({c,{s,d}});
    }
    // Kruskal法
    sort(es.begin(), es.end());
    uf.init(n);
    g.resize(n);
    for(int i=0;i<m;i++){
        auto e = es[i];
        int c = e.first, u = e.second.first, v = e.second.second;
        if(!uf.is_same(u,v)){  // 候補に加える
            uf.unite(u,v);
            noAlt[i] = true;
            g[u].push_back({v, i});  // 行先と辺番号のペア
            g[v].push_back({u, i});
        }
        else{
            // 閉路内でコストがcと同じ辺を候補から除く
            dfs(u, -1, v, c);
        }
    }
    int ecnt = 0, csum = 0;
    for(int i=0;i<m;i++){
        if(noAlt[i]){
            ecnt++;
            csum += es[i].first;
        }
    }
    cout << ecnt << " " << csum << endl;
    return 0;
}