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;

#define mk(a,b) make_pair(a,b)
#define se second
#define fi first

typedef pair<int, int> pii;
typedef pair<int, pii> iii;

int N, M;
vector<iii> edge;
vector<int> mem;

int par[510];

void init() {
    for(int i = 0; i <= N; i++) {
        par[i] = i;
    }
}

int root(int x) {
    if(par[x] == x)return x;
    return par[x] = root(par[x]);
}

bool same(int x, int y) {
    return root(x) == root(y);
}

void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if(x == y)return;
    par[x] = y;
}

int main() {
    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int s, d, c;
        cin >> s >> d >> c;
        edge.push_back(mk(c, mk(s, d)));
    }

    sort(edge.begin(), edge.end());

    int min_cost = 0;
    init();
    for(int i = 0; i < edge.size(); i++) {
        iii now = edge[i];
        int a = now.se.fi, b = now.se.se;
        int cost = now.fi;

        if(!same(a, b)) {
            unite(a, b);
            mem.push_back(i);
            min_cost += cost;
        }
    }

    int ans = 0;
    int ans_cost = 0;

    for(int j = 0; j < mem.size(); j++) {
        int now_cost = 0;
        int now_count = 0;
        init();
        for(int i = 0; i < edge.size(); i++) {
            if(i == mem[j])continue;

            iii now = edge[i];
            int a = now.se.fi, b = now.se.se;
            int cost = now.fi;

            if(!same(a, b)) {
                unite(a, b);
                now_cost += cost;
                now_count++;
            }
        }

        if(now_count != N - 1 || now_cost != min_cost) {
            ans++;
            ans_cost += edge[mem[j]].fi;
        }
    }

    cout << ans << " " << ans_cost << endl;

    return 0;
}