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 f first
#define s second
#define mp make_pair
#define inf 1<<30
using namespace std;

int n,m;
long long G[501][501];
vector<pair<int,int> > V;

long long Prim()
{
  priority_queue<pair<int,int> > PQ;
  long long d[501],color[501],parent[501];
  for(int i=0;i<n;i++){
    d[i]=inf;
    color[i]=0;
  }
  d[0]=0;
  parent[0]=0;
  PQ.push(make_pair(0,0));
  color[0]=0;
  while(!PQ.empty()){
    pair<int,int> p=PQ.top();PQ.pop();
    int u=p.s;
    color[u]=2;

    if(d[u]<p.f*(-1))continue;

    for(int i=0;i<n;i++){
      if(color[i]==2 || G[u][i]==inf)continue;
      if(d[i]>G[u][i]){
	d[i]=G[u][i];
	PQ.push(make_pair(d[i]*(-1),i));
	parent[i]=u;
	color[i]=1;
      }
    }
  }
  if(V.empty()){
    for(int i=1;i<n;i++){
      V.push_back(mp(i,parent[i]));
    }
  }
  long long res=0;
  for(int i=0;i<n;i++)res+=d[i];
  return res;
}  

int main()
{
  int x,y,c;
  cin>>n>>m;
  for(int i=0;i<501;i++)for(int j=0;j<501;j++)G[i][j]=inf;
  for(int i=0;i<m;i++){
    cin>>x>>y>>c;
    x--;y--;
    G[x][y]=c;
    G[y][x]=c;
  }
  long long sum=Prim(),sump=0,sumc=0;
  for(int i=0;i<V.size();i++){
    int tmp=G[V[i].f][V[i].s];
    G[V[i].f][V[i].s]=inf;
    G[V[i].s][V[i].f]=inf;
    long long a=Prim();
    if(sum<a){
      sump++;
      sumc+=tmp;
    }
    G[V[i].f][V[i].s]=tmp;
    G[V[i].s][V[i].f]=tmp;
  }
  cout<<sump<<" "<<sumc<<endl;
  return 0;
}