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<vector>
#include<utility>
#include<algorithm>
using namespace std;
struct UnionFind {
  int *data;
  UnionFind(int *_data, int size) : data(_data) {
    for(int i = 0; i < size; i++) data[i] = -1;
  }
  bool unionSet(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) {
      if (data[y] < data[x]) std::swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  int find(int x) {
    return data[x] < 0 ? x : data[x] = find(data[x]);
  }
  int size(int x) {
    return -data[find(x)];
  }
};
int main(int argc, char *argv[])
{
  // kruskal with x being unused.
  // assumption: es is sorted
  auto kruskal = [](int n, const vector<pair<int,pair<int,int>>> &es, int x, vector<bool> &used) {
    vector<int> ufdata(n);
    UnionFind uf(&(ufdata[0]), n);
    int sum = 0;
    for(int i = 0; i < es.size(); i++) {
      if(i == x) continue;
      const int u = es[i].second.first;
      const int v = es[i].second.second;
      if(uf.find(u) != uf.find(v)) {
        used[i] = true;
        uf.unionSet(u, v);
        sum += es[i].first;
      }
    }
    return sum;
  };
  int n, m;
  vector<pair<int,pair<int,int>>> es;
  cin >> n >> m;
  for(int i = 0; i < m; i++) {
    int s, d, c;
    cin >> s >> d >> c;
    es.push_back(make_pair(c, make_pair(s-1, d-1)));
  }
  sort(es.begin(), es.end());
  vector<bool> used(m, false);
  vector<bool> used2(m, false);
  int mn = kruskal(n, es, -1, used);
  int sum = 0;
  int cnt = 0;
  for(int i = 0; i < m; i++) {
    if(!used[i]) continue;
    int mni = kruskal(n, es, i, used2);
    if(mni != mn) {
      cnt ++;
      sum += es[i].first;
    }
  }
  cout << cnt << " " << sum << endl;
  return 0;
}