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 <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#define  M  50010
#define  N  600
using namespace std;
struct Edge {
       int u, v, weight, earse;
       Edge () {}
       Edge (int a,int b,int c): u(a), v(b), weight(c), earse(0) {}
} edge[M];
int visit[M], parent[N], n, m, first, cnt, sum;
bool operator<(const Edge &a,const Edge &b) { return a.weight<b.weight; }
int find(int x) {
    int r,t;
    for (r=x;parent[r]>0;r=parent[r])
        ;
    while (parent[x] > 0) {
          t = parent[x];
          parent[x] = r;
          x = t;
    }    
    return r;
}
void weight_union(int u,int v) {
    int i = find(u);
    int j = find(v);
    if (i == j) 
      return ;
    if (parent[i] < parent[j]) {
       parent[i] += parent[j];
       parent[j] = i; 
    }  
    else  {
       parent[j] += parent[i];
       parent[i] = j;
    }
}
int kruskal (void) {
     memset (parent,-1,sizeof(parent));
     int mst = 0;
     for (int i=0,j=0;i<n-1;++i) {
         while (j<m && (edge[j].earse || find(edge[j].u) == find(edge[j].v))) ++j;
         if (j == m)
            return mst;
         mst += edge[j].weight;
         weight_union(edge[j].u,edge[j].v);
         if (first) 
            visit[j] = 1;
         ++j;   
     }
     return mst;
}
void solve (void) {
    memset (visit,0,sizeof(visit));
    sort (edge,edge+m);
    first = 1;
    int mst = kruskal();
    first = 0;
    cnt = sum = 0;
    for (int i=0;i<m;++i)
        if (visit[i]) {
           edge[i].earse = 1;
           int tmp = kruskal();
           if (tmp != mst) {
              cnt++;
              sum+=edge[i].weight;
           } 
           edge[i].earse = 0;
        }
}
int main(void) {
    int u, v, w;
    while ( scanf("%d%d",&n,&m)==2 ) {
          for (int i=0;i<m;++i) {
              scanf ("%d%d%d",&u,&v,&w);
              edge[i] = Edge(u,v,w);     
          }
          solve ();
          printf ("%d %d\n",cnt,sum);
    }
    return 0;
}