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 <vector>
#include <algorithm>
using namespace std;

struct UnionFindTree{
    vector<int> v;
    vector<int> rank;
     
    UnionFindTree(int n): v(n, -1), rank(n, 0){}
    int Find(int x){
        if(v[x] < 0) return x;
        return v[x] = Find(v[x]);
    }
    void Union(int a, int b){
        a = Find(a);
        b = Find(b);
        if(a == b) return;
        if(rank[a] < rank[b]) swap(a, b);
        if(rank[a] == rank[b]) rank[a]++;
        v[b] = a;
    }
};

struct edge{
    int a,b,d;
    bool operator<(const edge &x) const{
        return d < x.d;
    }
};
    
int mst(vector<edge> &e, vector<int> &use, int skip = -1){
    int m = e.size();
    UnionFindTree uft(m);
    int res = 0;
    for(int i=0; i<m; i++){
        if(i == skip) continue;
        if(uft.Find(e[i].a) != uft.Find(e[i].b)){
            uft.Union(e[i].a, e[i].b);
            if(skip == -1) use.push_back(i);
            res += e[i].d;
        }
    }
    return res;
}
 
int main(){
    int n,m;
    cin >> n >> m;
    vector<edge> e(m);
    for(int i=0; i<m; i++){
        cin >> e[i].a >> e[i].b >> e[i].d;
        e[i].a--; e[i].b--;
    }
    sort(e.begin(), e.end());

    vector<int> use;
    int mincost = mst(e, use);
    int num=0, cost=0;
    for(size_t i=0; i<use.size(); i++){
        if(mincost != mst(e, use, use[i])){
            num++;
            cost += e[use[i]].d;
        }
    }
    cout << num << " " << cost << endl;
    return 0;
}