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;

struct Edge {
  int u, v, c;
  Edge() {}
  Edge(int u, int v, int c) :
    u(u), v(v), c(c) {}
  bool operator < (const Edge& e) const {
    return c < e.c;    
  }
};

struct UnionFind {
  int n;
  vector<int> r, p;
  UnionFind() {}
  UnionFind(int sz) : n(sz), r(sz, 1), p(sz, 0) {
    iota(p.begin(), p.end(), 0);    
  }
  int find(int x) {
    return (x==p[x] ? x : p[x]=find(p[x]));    
  }
  bool same(int x, int y) {
    return find(x) == find(y);    
  }
  void unite(int x, int y) {
    x = find(x); y = find(y);
    if ( x == y ) return;
    if ( r[x] < r[y] ) swap(x, y);
    r[x] += r[y];
    p[y] = x;    
  }
};

int main() {
  int N, M;
  cin >> N >> M;
  
  vector<Edge> es(M);  
  for ( int i = 0; i < M; i++ ) {
    int u, v, c;
    cin >> u >> v >> c;
    u--; v--;
    es[i] = Edge{u, v, c};    
  }

  sort(es.begin(), es.end());  

  vector<int> use;
  int cost = 0;
  {
    UnionFind uf(N);
    int cnt = 0;
    for ( int i = 0; i < M; i++ ) {
      int u = es[i].u, v = es[i].v, c = es[i].c;
      if ( uf.same(u, v) ) continue;
      cost += c;
      uf.unite(u, v);
      use.emplace_back(i);
      cnt++;
      if ( cnt == N-1 ) continue;    
    }
  }

  int ans = 0, anscost = 0;  
  for ( int i = 0; i < N-1; i++ ) {
    UnionFind uf(N);
    int ncost = 0;
    int ncnt = 0;    
    for ( int j = 0; j < M; j++ ) {
      if ( use[i] == j ) continue;
      int u = es[j].u, v = es[j].v, c = es[j].c;
      if ( uf.same(u, v) ) continue;
      ncost += c;
      uf.unite(u, v);
      ncnt++;
      if ( ncnt == N-1 ) continue;      
    }

    if ( ncost > cost || ncnt < N-1 ) {
      ans++;
      anscost += es[use[i]].c;      
    }
  }

  cout << ans << " " << anscost << endl;
  
  return 0;
}