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;

#define MAX 510
#define MAX_E 50010

int par[MAX],rnk[MAX];
void init(int N){
  for(int i = 0 ; i < N ; i++){
    par[i] = i;
    rnk[i] = 0;
  }
}

int find(int x){
  if(par[x] == x){
    return x;
  }
  return par[x] = find(par[x]);
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y){ return; }
  if(rnk[x] < rnk[y]){
      par[x] = y;
  }else{
    par[y] = x;
    if(rnk[x] == rnk[y]){
      rnk[x]++;
    }
  }
}

bool same(int x,int y){
  return (find(x) == find(y));
}

struct Edge{ int u,v,cost; };

bool comp(const Edge &e1,const Edge &e2){
  return e1.cost < e2.cost;
}

int V,E;
Edge es[MAX_E];

bool equals(const Edge &e1,const Edge &e2){
  return (e1.u == e2.u && e1.v == e2.v);
}

vector<Edge> vec;

int kruskal(int ne){
  init(V);
  int res = 0;
  for(int i = 0 ; i < E ; i++){
    Edge e = es[i];
    if(ne != -1 && equals(e,vec[ne])){
      continue;
    }
    if(!same(e.u,e.v)){
      unite(e.u,e.v);
      res += e.cost;
    }
  }
  return res;
}

int kruskal(){
  sort(es,es+E,comp);
  init(V);
  int res = 0;
  for(int i = 0 ; i < E ; i++){
    Edge e = es[i];
    if(!same(e.u,e.v)){
      unite(e.u,e.v);
      res += e.cost;
      vec.push_back(e);
    }
  }
  return res;
}

int main(){
  int a,b,c;
  cin >> V >> E;
  for(int i = 0 ; i < E ; i++){
    cin >> a >> b >> c; a--; b--;
    es[i] = (Edge){a,b,c};
  }
  vec.clear();
  int cnt = 0, sum = 0;
  int res = kruskal();
  for(int i = 0 ; i < (int)vec.size() ; i++){
    int r = kruskal(i);
    bool check = true;
    for(int j = 0 ; j < V ; j++){
      if(!same(0,j)){
        check = false;
        break;
      }
    }
    if((check && r > res) || !check){
      cnt++;
      sum += vec[i].cost;
    }
  }
  cout << cnt << " " << sum << endl;
  return 0;
}