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;
using ll = long long;
using pii = pair<int, int>;

template <class T>
struct Kruskal {
  struct UnionFind {
    int N;
    vector<int> sz_tree, parent;
    UnionFind() {}
    UnionFind(int N) : N(N), sz_tree(N, 1), parent(N) {
      iota(parent.begin(), parent.end(), 0);
    }
    int root(int x) {
      return parent[x] == x ? x : parent[x] = root(parent[x]);
    }
    void merge(int x, int y) {
      if ((x = root(x)) == (y = root(y))) return;
      if (sz_tree[x] < sz_tree[y]) swap(x, y);
      sz_tree[x] += sz_tree[y];
      parent[y] = x;
    }
    bool same(int x, int y) {
      return root(x) == root(y);
    }
    int size(int x) {
      return sz_tree[root(x)];
    }
  };
  struct edge {
    int from, to; T cost; bool used;
    edge() {}
    edge(int f, int t, T c) : from(f), to(t), cost(c) {
      used = false;
    }
  };
 
  int N;
  vector<edge> es;
  Kruskal() {}
  Kruskal(int N) : N(N) {}
 
  void add_edge(int from, int to, T cost) {
    es.emplace_back(from, to, cost);
  }
  T mst() {
    T res = 0;
    UnionFind uf(N);
    sort(es.begin(), es.end(), [&](edge a, edge b) {
      return a.cost < b.cost;
    });
    for (auto &e : es) {
      if (uf.same(e.from, e.to)) continue;
      uf.merge(e.from, e.to);
      e.used = true;
      res += e.cost;
    }
    return res;
  }
  T query(edge e2) {
    T res = 0;
    UnionFind uf(N);
    for (auto &e : es) {
      if (e.from == e2.from && e.to == e2.to) continue;
      if (uf.same(e.from, e.to)) continue;
      uf.merge(e.from, e.to);
      res += e.cost;
    }
    return res;
  }
};

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int N, M;
  cin >> N >> M;
  Kruskal<int> K(N);
  for (int i = 0; i < M; i++) {
    int S, D, C;
    cin >> S >> D >> C;
    S--, D--;
    K.add_edge(S, D, C);
  }
  int mst = K.mst(), cnt = 0, sum = 0;
  for (auto &e : K.es) {
    if (e.used && K.query(e) != mst) {
      cnt++, sum += e.cost;
    }
  }
  cout << cnt << " " << sum << endl;

  return 0;
}