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 <unordered_map>
#include <algorithm>

using namespace std;

const int MAX = 505;

int d[MAX + 1];

void init() {
    for(int i = 1; i <= MAX; ++i){
        d[i] = i;
    }
}

int find(int n) {
    return (d[n] == n) ? d[n] : d[n] = find(d[n]);
}

bool Union(int a, int b) {
    int x = find(a);
    int y = find(b);
    if(x != y) d[x] = y;
    return x != y;
}

struct E {
    E(int len = 0, int node1 = 0, int node2 = 0):len(len), node1(node1), node2(node2){}
    int len, node1, node2;

};

bool cmp(const E& l, const E& r){
    return l.len < r.len;
}

vector<E> edge, mst;

pair<int, int> kruskal(vector<E>& v, bool make_mst = false)
{
    init();
    sort(v.begin(), v.end(), cmp);
    int res = 0, num = 0;
    for(auto& e : v){
        if(Union(e.node1, e.node2)){
            if(make_mst) mst.push_back(e);
            res += e.len;
            num++;
        }
    }
    return make_pair(res, num);
}

int main()
{
    cin.tie(0);
    cin.sync_with_stdio(0);
    int N, M;
    cin >> N >> M;
    int S, D, C;
    for(int i = 0; i < M; ++i){
        cin >> S >> D >> C;
        edge.push_back(E(C, S, D));
        edge.push_back(E(C, D, S));
    }
    int mst_len = kruskal(edge, true).first;
    int num = 0, len = 0;
    for(auto& e : mst){
        vector<E> v;
        for(auto& i : edge){
            if((e.node1 == i.node1 && e.node2 == i.node2) ||
               (e.node1 == i.node2 && e.node2 == i.node1)) continue;
            v.push_back(i);
        }
        auto res = kruskal(v);
        if(res.second < N - 1 || res.first > mst_len){
            num++;
            len += e.len;
        }
    }
    cout << num << " " << len << endl;
}