Problem: Example

Input

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


Output

1 3

Solution (in CPP):

Solution:
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;

struct edge {
    int u, v;
    int64_t cost;
    edge(int u=0, int v=0, int64_t cost=0):u(u), v(v), cost(cost) {} 
};

struct Edge {
    int to;
    int64_t cost;
    Edge(int x=0, int64_t y=0):to(x), cost(y) {}
};

vector<vector<Edge> > G; // resizeの必要あり
map<P, bool> checked;

int dfs(int i, int j, Edge& X) {
    //cout << i << endl;
    if(i == X.to) {
        return 0;
    }
    bool flag = false;
    int cou = 0;
    for(auto next:G[i]) {
        if(next.to == j) continue;
        int v = dfs(next.to, i, X);
        if(v == -1) continue;
        flag = true;
        cou += v;
        if(next.cost == X.cost && !(checked[P(i, next.to)]))  {
            checked[P(next.to, i)] = checked[P(i, next.to)] = true;
            cou++;
        }
    }
    if(flag) return cou;
    else return -1;
}

struct UnionFind {
    vector<int> par; // 親を指すvector,-par[親]は木のサイズ
    UnionFind(int n):par(n, -1) {} // uniteで親を埋め込んでいく必要あり
    int root(int x) { // 親をたどる&データの整理
        if(par[x] < 0) {
            return x;
        }
        return 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]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    bool same(int x, int y) {
        x = root(x);
        y = root(y);
        return (x == y);
    } // 所属判定
    int size(int x) {return -par[root(x)];} // 木のサイズ
};



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

int ans=0;

vector<edge> es; // 辺の数でresize
//最小全域木
int64_t kruskal(int V) { // Vは頂点数
    int E = es.size();
    sort(es.begin(), es.end(), comp);
    UnionFind uft(V);
    int64_t res = 0;
    for(int i = 0; i < E; ++i) {
        edge e = es[i];
        //cout << e.u << ' ' << e.v << endl;
        G[e.u].push_back(Edge(e.v, e.cost));
        G[e.v].push_back(Edge(e.u, e.cost));
        if(!uft.same(e.u, e.v)) {
            uft.unite(e.u, e.v);
            res += e.cost;
            ++ans;
            
        } else {
            Edge X = Edge(e.u, e.cost);
            int gg = dfs(e.v, e.u, X);
            G[e.u].pop_back();
            G[e.v].pop_back();
            ans -= gg;
            res -= gg*e.cost;
        }
    }
    return res;
}






int main() {
    int n, m;
    cin >> n >> m;
    es.resize(m);
    G.resize(n);
    rep(i, m) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        --a;
        --b;
        es[i] = edge(a, b, c);
    }
    int kk = kruskal(n);
    cout << ans << ' ';
    cout << kk << endl;
}