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 MAX_N 6500000
#define rank Asdfiasofsad
using namespace std;

struct edge{
  int c,a,b;
  bool operator < (edge x)const{return c<x.c;}
};

int par[MAX_N];
int rank[MAX_N];
int n,m;
edge e[50000];
bool used[50000];
void init(int n){
  for(int i=0;i<n;i++){
    par[i]=i;
    rank[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(rank[x]<rank[y])par[x]=y;
  else{
    par[y]=x;
    if(rank[x]==rank[y])rank[x]++;
  }
}

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

int cal(int x){
  int res=0,c=0;
  init(n);
  for(int i=0;i<m;i++){
    if(i==x||same(e[i].a,e[i].b))continue;
    if(x==-1)used[i]=1;
    unite(e[i].a,e[i].b);
    res+=e[i].c,c++;
  }
  return c==n-1?res:0;
}

int main(){
  cin>>n>>m;
  for(int i=0;i<m;i++){
    cin>>e[i].a>>e[i].b>>e[i].c;
    e[i].a--,e[i].b--;
  }
  sort(e,e+m);
  int cnt=0,ans=0,mn=cal(-1);
  for(int i=0;i<m;i++)
    if(used[i]&&cal(i)!=mn)ans+=e[i].c,cnt++;
  cout<<cnt<<" "<<ans<<endl;
  return 0;
}