Problem: Example

Input

4 4
1 2 3
1 3 3
2 3 3
2 4 3


Output

1 3

Solution (in CPP):

Solution:
// 5/26
// 2-5-3 最小全域木
// 類題 There is no alternative
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1350&lang=en
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

// UnionFind
struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};

// クラスカル法ではグラフは辺の集合として定義（無向が前提）
struct Edge {
    int u;
    int v;
    int cost;
    Edge(int u, int v, int c) : u(u), v(v), cost(c) { }
    // Edge(int u_, int v_, int c) : u(u_), v(v_), cost(c) { }
    // Edge(int u, int v, int c) {
    //     this->u = u;
    //     this->v = v;
    //     this->cost = c;
    // }
    bool operator<(const Edge& o) const {
        return cost < o.cost;
    }
};
using Graph = vector<Edge>;

int kruskal(int N, Graph& es, Edge pass, vector<Edge>& candidates) {  // ここでconstはだめ。ソートするから。いっぱいエラー出る。http://nocotan.github.io/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0/2017/01/27/mst-copy.html
    sort(es.begin(), es.end());
    UnionFind uf(N);
    
    int res = 0;
    // int num_e = 0;  // 引かれる辺の数

    // for (auto e : es) {
    rep(i, es.size()) {
        // if (i == pass) continue;
        Edge e = es[i];
        if (e.u == pass.u && e.v == pass.v) continue;

        if (!uf.same(e.u, e.v)) {
            uf.unite(e.u, e.v);
            res += e.cost;
            // num_e++;
            candidates.push_back(e);  // i
        }
    }

    // if (num_e == N - 1) {
    //     return res;
    // } else {
    //     return -1;
    // }
    return res;
}

int main() {
    int N, M;
    cin >> N >> M;

    Graph es;

    rep(i, M) {
        int s, d, c;
        cin >> s >> d >> c;
        s--; d--;
        es.push_back(Edge(s, d, c));
    }

    vector<Edge> candidates;  // 最短経路候補の辺のes通し番号を格納
    int min_cost = kruskal(N, es, Edge(-1, -1, -1), candidates);

    // printf("candidates size is %d\n", candidates.size());

    int ans_num = 0;
    int ans_cost = 0;

    // rep(i, M) {
    //     int cost = kruskal(N, es, i);
    //     // if (cost != min_cost && cost == -1) {
    //     if (cost == -1 || (cost != -1 && cost != min_cost)) {
    //         ans_num++;
    //         ans_cost += es[i].cost;
    //     }
    // }

    rep(i, candidates.size()) {
        // cout << candidates.size() << endl;
        vector<Edge> dummy;
        int cost = kruskal(N, es, candidates[i], dummy);
        // printf("i, candidates[i], cost, min_cost = %d, %d, %d, %d\n", i, candidates[i], cost, min_cost);
        if (cost != min_cost) {
            ans_num++;
            // ans_cost += es[i].cost;
            ans_cost += candidates[i].cost;
        }
    }

    cout << ans_num << " " << ans_cost << endl;
}