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;
const int INF = 1 << 30;
class DisjointSet{
private:
  vector<int> rank, p;
  void link(int x,int y){
    if(rank[x] > rank[y]){
      p[y] = x;
    }else{
      p[x] = y;
      if(rank[x] == rank[y]) rank[y]++;
    }
  }
public:
  DisjointSet(int size){
    rank.resize(size,0);
    p.resize(size,0);
  }
  void build(){
    for(int i = 0; i < rank.size(); i++){
      makeSet(i);
    }
  }
  void makeSet(int x){
    p[x] = x, rank[x] = 0;
  }
  void Union(int x,int y){
    if(findSet(x) != findSet(y))
      link(findSet(x),findSet(y));
  }
  int findSet(int x){
    return( x != p[x] ? p[x] = findSet(p[x]) : p[x]);
  }
};

struct edge{
  int u, v, cost;
  bool operator<(const edge& hoge)const{
    return cost < hoge.cost;
  }
};
typedef vector< edge > Edges;
void add_edge(Edges& info, int u, int v, int cost){
  info.push_back( (edge){ u, v, cost});
}
bool used[50000];

int kruskal(Edges& edges, int V, int donot){
  DisjointSet uf_tree(V); uf_tree.build();
  int ret = 0;
  for(int i = 0; i < edges.size(); i++){
    edge& e = edges[i];
    if(i != donot && uf_tree.findSet(e.u) != uf_tree.findSet(e.v)){
      uf_tree.Union( e.u, e.v);
      ret += e.cost;
      if(donot == -1) used[i] = true;
    }
  }
  return ret;
}

int main(){
  int N, M;
  cin >> N >> M;
  Edges edges;
  for(int i = 0; i < M; ++i){
    int u, v, c;
    cin >> u >> v >> c;
    --u, --v;
    add_edge( edges, u, v, c);
  }
  sort( edges.begin(), edges.end());
  int get = kruskal( edges, N, -1);
  int a = 0, b = 0;
  for(int i = 0; i < edges.size(); ++i){
    if(used[i] && kruskal( edges, N, i) != get){
      ++a, b += edges[i].cost;
    }
  }
  cout << a << " " << b << endl;
}