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;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define mp(x) make_pair((x))
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using P = pair<pair<long,int>,pair<int,int>>;

class UnionFind{
public:
    vector<int> par,rank;
    UnionFind(int sz) : par(sz, -1), rank(sz,0){}
    int find(int x){
        if(par[x]<0) 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]){
            par[y] += par[x];
            par[x] = y;
        }
        else {
            par[x] += par[y];
            par[y] = x;
            if(rank[x]==rank[y]) rank[x]++;
        }
    }
    bool same(int x,int y){ return find(x)==find(y); }
    int size(int x){ return -par[find(x)]; }
};

int main()
{
    int n,m;
    cin>>n>>m;
    vector<P> vec(m);
    vector<int> costs(m);
    rep(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        a--;b--;
        vec[i] = P({c,i},{a,b});
        costs[i] = c;
    }
    sort(all(vec));

    vector<bool> use(m,false);
    auto mst = [&](int notuse=-1){
        UnionFind uf(n);
        long res = 0;
        rep(i,m){
            auto p = vec[i];
            if(vec[i].fi.se == notuse) continue;
            int v = vec[i].se.fi;
            int u = vec[i].se.se;
            if(uf.same(u,v)) continue;
            else {
                use[vec[i].fi.se] = true;
                uf.unite(u,v);
                res += vec[i].fi.fi;
                if(uf.size(0)==n) break;
            }
        }
        if(uf.size(0)<n) return 123456789012678L;
        return res;
    };


    long total = mst();
    vector<int> cand;
    rep(i,m)if(use[i]) cand.pb(i);

    int a1=0;
    long a2 = 0;
    for(auto i : cand){
        long nc = mst(i);
        if(nc > total){
            a1++;
            a2 += costs[i];
        }
    }


    cout << a1 << " " << a2 << endl;

    return 0;
}