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 r(i,n) for(int i=0;i<n;i++)
typedef pair<int,int>P;
#define F first
#define S second
int n,m,a1,a2,a3;
int par[10001];
int rak[10001];
void init(int n){
  for(int i=0;i<n;i++){
    par[i]=i;
    rak[i]=1;
  }
}
int find(int x){
  if(par[x]==x){
    return x;
  }else{
    return par[x]=find(par[x]);
  }
}
void unit(int x,int y){
  x=find(x);
  y=find(y);
  if(x==y)return;
  if(rak[x]<rak[y]){
    par[x]=y;
  }else{
    par[y]=x;
    if(rak[x]==rak[y])rak[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;
}
edge es[100001],e;
int ans;
vector<edge>v;
int V,E;
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)){
      unit(e.u,e.v);
      v.push_back(e);
      res+=e.cost;
    }
  }
  ans=res;
  return res;
}
int kruskal2(edge now){
  sort(es,es+E,comp);
  init(V);
  int res=0,res1=0;
  for(int i=0;i<E;i++){
    edge e=es[i];
    if(e.v==now.v&&e.u==now.u&&e.cost==now.cost)continue;
    if(!same(e.u,e.v)){
      unit(e.u,e.v);
      res++;
      res1+=e.cost;
    }
  }
  return res!=n-1||ans!=res1;
}
int main(){
  int ans1=0,ans2=0;
  cin>>n>>m;
  r(i,m){
    cin>>a1>>a2>>a3;
    e.u=a1,e.v=a2,e.cost=a3;
    es[i]=e;
  }
  E=m;V=n+1;
  kruskal();
  r(i,v.size()){
    if(kruskal2(v[i])){
      //cout<<v[i].u<<endl;
      ans1++;
      ans2+=v[i].cost;
    }
  }
  cout<<ans1<<' '<<ans2<<endl;
}