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;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<ll> Size;
    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n + 1); rank.resize(n + 1); Size.resize(n + 1);
        for (int i = 0; i <= n; ++i) par[i] = i, rank[i] = 0, Size[i] = 1;
    }

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

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

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        Size[x] += Size[y];
        return true;
    }

    ll size(int x){
        return Size[root(x)];
    }
};

int N, M;
typedef pair<int, i_i> iii;
map<i_i, int> mp;
int S[50000], D[50000], C[50000];
vector<iii> paths[500];
vector<iii> que;
vector<iii> rest;

bool ans[50000];

bool dfs(int now, int from, int destination, int cost) {
    if(now == destination) return true;
    for(auto tmp : paths[now]) {
        int to = tmp.first;
        int nowcost = tmp.second.first;
        int e = tmp.second.second;
        if(to == from) continue;
        if(dfs(to, now, destination, cost)) {
            if(nowcost == cost) {
                ans[e] = false;
            }
            return true;
        }
    }
    return false;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        cin >> S[i] >> D[i] >> C[i];
        S[i]--;
        D[i]--;
        mp[{S[i], D[i]}] = i;
        que.push_back({C[i], {S[i], D[i]}});
    }
    UnionFind uni(N);
    sort(que.begin(), que.end());
    for(auto tmp : que) {
        int s = tmp.second.first;
        int t = tmp.second.second;
        if(uni.merge(tmp.second.first, tmp.second.second)) {
            paths[s].push_back({t, {tmp.first, mp[{s, t}]}});
            paths[t].push_back({s, {tmp.first, mp[{s, t}]}});
            ans[mp[{s, t}]] = true;
        } else {
            rest.push_back(tmp);
        }
    }
    /*
    for(int i = 0; i < M; i++) {
        if(ans[i]) cerr << i << " ";
    }
    cerr << endl;
    */
    for(auto tmp : rest) {
        dfs(tmp.second.first, -1, tmp.second.second, tmp.first);
    }
    int ansnum = 0;
    int anscost = 0;
    for(int i = 0; i < M; i++) {
        if(ans[i]) {
            ansnum++;
            anscost += C[i];
        }
    }
    cout << ansnum << " " << anscost << endl;
    return 0;
}