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>

#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;
struct UnionFind {
  vector<int> parent;
  UnionFind (int n) { parent.assign(n, -1); }
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
  bool merge(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (parent[y] < parent[x]) swap(x, y);
    if (parent[x] == parent[y]) --parent[x];
    parent[y] = x;
    return true;
  }
};
typedef int Weight;
struct Edge{
  int src, dest; Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
  bool operator != (const Edge &rhs) const {return src != rhs.src || dest != rhs.dest;}
};

typedef vector<Edge> Edges;

// Kruskal
// N, operator <
Edges kruskal(int V, Edges &es) {
  UnionFind uf(V);
  Edges res;
  REP(i, es.size()) {
    Edge e = es[i];
    if(uf.root(e.src) != uf.root(e.dest)) {
      uf.merge(e.src, e.dest);
      res.push_back(e);
    }
  }
  return res;
}

int main() {
  int n,m;
  cin>>n>>m;
  Edges es;
  REP(i,m){
    int s,t,c;
    cin>>s>>t>>c;
    --s;--t;
    es.push_back((Edge){s,t,c});
  }
  sort(es.rbegin(), es.rend());
  auto mst = kruskal(n, es);
  int csum = 0;
  for(auto e:mst) csum += e.weight;
  int cnt = 0, esum = 0;
  REP(i,n-1) {
    Edges ee;
    REP(j,m) if(es[j]!=mst[i]) ee.push_back(es[j]);
    auto mst2 = kruskal(n, ee);
    int ccsum = 0;
    for(auto e:mst2) ccsum += e.weight;
    if (ccsum != csum) {
      ++cnt;
      esum += mst[i].weight;
    }
  }
  cout << cnt << ' ' << esum << endl;
  return 0;
}