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;
const int maxn = 50010;
struct node 
{
      int u,v,w;
      bool used,mark,del;
      node(int x = 0,int y = 0,int z = 0) 
	  {
        u = x;
        v = y;
        w = z;
        mark = del = used = false;
     }
     bool operator<(const node &tmp) const 
	 {
         return w < tmp.w;
     }
 }e[maxn];
 int uf[maxn],n,m,cnt;
 bool flag[maxn];
 int find(int x) {
     return uf[x] = uf[x] == x?uf[x]:find(uf[x]);
 }
 int kruskal(bool &Unique,bool first) {
     int ans = cnt = 0;
     for(int i = 0; i <= n; ++i) uf[i] = i;
     for(int i = 0; i < m; ++i) {
        if(!first && e[i].del) continue;
        int fx = find(e[i].u);
        int fy = find(e[i].v);
       if(fx != fy)
	   {
    	   	uf[fx] = fy;
            ans += e[i].w;
            if(first) 
			{
            e[i].used = true;
            if(e[i].mark) Unique = false;
            }
            if(++cnt == n-1) return ans;
	   }
     }
     return ans;
 }
 int main() {
     int u,v,w;
    // freopen("data.in","r",stdin); 
     while(~scanf("%d %d",&n,&m)) {
         for(int i = 0; i < m; ++i) {
             scanf("%d %d %d",&u,&v,&w);
             e[i] = node(u,v,w);
         }
         memset(flag,false,sizeof(flag));
         sort(e,e+m);
         for(int i = 1; i < m; ++i)
             if(e[i].w == e[i-1].w) e[i].mark = e[i-1].mark = true;
         bool Unique = true;
         int MST = kruskal(Unique,1);
         if(Unique) printf("%d %d\n",cnt,MST);
         else {
             int res1 = 0,res2 = 0;
             for(int i = 0; i < m; ++i) {
                 if(e[i].used && e[i].mark) {
                     e[i].del = true;
                     int mst = kruskal(Unique,0);
                     if(mst == MST && cnt == n-1) flag[i] = true;
                     e[i].del = false;
                 }
               if(e[i].used && !flag[i]) {
                     res1++;
                     res2 += e[i].w;
                 }
             }
             printf("%d %d\n",res1,res2);
        }
     }
     return 0;
 }