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 <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < (int)N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

using P = pair<int, int>;

class UnionFind
{
public:
    vs32 p;

    UnionFind() {}
    UnionFind(int size)
    : p(vs32(size, -1))
    {}

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

    void unite(int x, int y)
    {
        x = findSet(x); y = findSet(y);
        if (x == y) return;

        if (p[x] > p[y]) swap(x, y);
        p[x] += p[y];
        p[y] = x;
    }

    int findSet(int x)
    {
        if (p[x] < 0) return x;
        else return p[x] = findSet(p[x]);
    }
};

int kruskal(int n, vector< pair<int, P> >& edge, int ng)
{
    int ret = 0;
 
    UnionFind uf(n);
    rep (i, edge.size())
    {
        int u, v, c;
        c = edge[i].first;
        u = edge[i].second.first;
        v = edge[i].second.second;
        if (i == ng || uf.same(u, v)) continue;

        uf.unite(u, v);
        ret += c;
    }

    return ret;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector< pair<int, P> > edge(m);
    rep (i, m)
    {
        int s, d, c;
        cin >> s >> d >> c;
        --s, --d;
        edge[i] = make_pair(c, P{s, d});
    }

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

    int cost = 0;
    UnionFind uf(n);
    vs32 ng;
    rep (i, m)
    {
        int u, v, c;
        c = edge[i].first;
        u = edge[i].second.first;
        v = edge[i].second.second;
        if (!uf.same(u, v))
        {
            uf.unite(u, v);
            ng.push_back(i);
            cost += c;
        }
    }

    int num = 0;
    int ans = 0;
    rep (i, ng.size())
    {
        if (cost != kruskal(n, edge, ng[i]))
        {
            ++num;
            ans += edge[ng[i]].first;
        }
    }

    cout << num << " " << ans << "\n";
    return 0;
}