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 int Weight;
const Weight INF = 1e9;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int f, int t, Weight c) :
        src(f), dst(t), weight(c) {}
};
bool operator<(const Edge &a, const Edge &b) {
    return a.weight != b.weight ? a.weight > b.weight :
        a.src != b.src ? a.src < b.src : a.dst < b.dst;
}
bool operator>(const Edge &a, const Edge &b) { return b < a; }

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

struct UnionFind
{
    vector<int> data;

    UnionFind(int size) : data(size, -1) { }

    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }

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

    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }

    int size(int x) {
        return -data[root(x)];
    }
};

// g: グラフ
// 戻り値: 最小全域森の重みと最小全域森の辺集合のペア
pair<Weight, Edges> Kruskal(const Graph &g) {
    int n = g.size();
    UnionFind uf(n);
    priority_queue<Edge> que;

    for (int u = 0; u < n; ++u)
        for (auto e = g[u].begin(); e != g[u].end(); ++e)
            if (u < e->dst)
                que.push(*e);

    Weight total = 0;
    Edges F;
    while (F.size() < (size_t)(n - 1) && !que.empty()) {
        Edge e = que.top();  que.pop();
        if (uf.unionSet(e.src, e.dst)) {
            F.push_back(e);
            total += e.weight;
        }
    }

    return pair<Weight, Edges>(total, F);
}

bool Find(const Graph &g, const Edges &edges,
          UnionFind &uf, Weight cost) {
    const int N = g.size();
    const int M = edges.size();

    for (int v = 0; v < N; ++v) {
        for (auto e : g[v]) {
            if (e.weight != cost)
                continue;

            bool flag = true;
            for (int i = 0; i < M; ++i)
                if ((e.src == edges[i].src && e.dst == edges[i].dst) ||
                    (e.dst == edges[i].src && e.src == edges[i].dst)) {
                    flag = false;
                    break;
                }

            if (flag) {
                if (!uf.findSet(e.dst, e.src))
                    return false;
            }
        }
    }
    return true;
}

int main()
{
    int N, M, S, D, C;

    // Make Graph
    cin >> N >> M;
    Graph g(N);
    for (int i = 0; i < M; ++i) {
        cin >> S >> D >> C;
        --S;
        --D;
        g[S].push_back(Edge(S, D, C));
        g[D].push_back(Edge(D, S, C));
    }

    int num = 0, sum = 0;
    pair<Weight, Edges> ans = Kruskal(g);
    int m = ans.second.size();

    for (int i = 0; i < m; ++i) {
        Weight cost = ans.second[i].weight;
        UnionFind uf(N);

        for (int j = 0; j < m; ++j) {
            if (i == j)
                continue;
            uf.unionSet(ans.second[j].src, ans.second[j].dst);
        }

        if (Find(g, ans.second, uf, cost)) {
            ++num;
            sum += cost;
        }
    }

    cout << num << " " << sum << endl;

    return 0;
}