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>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;

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

struct UnionFind{
    vector<int> par, sz;
    UnionFind(int n){
        par.resize(n);
        sz.resize(n, 1);
        for(int i = 0; i < n; i++) par[i] = i;
    }
    int find(int x){
        if(x == par[x]) return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y){
        x = find(x); y = find(y);
        if(x == y) return;
        if(sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y];
        par[y] = x;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
};

int n, m;
vector<edge> es; 

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    es.resize(m);
    rep(i, 0, m){
        cin >> es[i].u >> es[i].v >> es[i].c;
        es[i].u--; es[i].v--;
    }
    vector<bool> use(m);
    UnionFind uf(n);
    sort(es.begin(), es.end());
    int sum = 0;
    rep(i, 0, m){
        if(!uf.same(es[i].u, es[i].v)){
            uf.unite(es[i].u, es[i].v);
            sum += es[i].c;
            use[i] = true;
        }
    }
    rep(i, 0, m){
        if(use[i] == false) continue;
        UnionFind uf2(n);
        int tmpSum = 0;
        rep(j, 0, m){
            if(j == i) continue;
            if(!uf2.same(es[j].u, es[j].v)){
                uf2.unite(es[j].u, es[j].v);
                tmpSum += es[j].c;
            }
        }
        if(sum == tmpSum){
            use[i] = false;
        }
    }
    int ans = 0, cost = 0;
    rep(i, 0, m){
        if(use[i]){
            ans++;
            cost += es[i].c;
        }
    }
    cout << ans << ' ' << cost << endl;
}