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 = 500000;
  struct arc {
      int u,v,w;
      bool used,mark,del;
      arc(int x = 0,int y = 0,int z = 0) {
          u = x;
         v = y;
         w = z;
         mark = del = used = false;
     }
     bool operator<(const arc &tmp) const {
         return w < tmp.w;
     }
 } e[maxn];
 int uf[maxn],n,m,cnt;
 bool nui[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) continue;
       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;
     while(~scanf("%d %d",&n,&m)) {
         for(int i = 0; i < m; ++i) {
             scanf("%d %d %d",&u,&v,&w);
             e[i] = arc(u,v,w);
         }
         memset(nui,false,sizeof(nui));
         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,true);
         if(Unique) printf("%d %d\n",n-1,MST);
         else {
             int mst = 0,ne = 0;
             for(int i = 0; i < m; ++i) {
                 if(e[i].used && e[i].mark) {
                     e[i].del = true;
                     int tmp = kruskal(Unique,false);
                     if(tmp == MST && cnt == n-1) nui[i] = true;
                     e[i].del = false;
                 }
               if(e[i].used && !nui[i]) {
                     ne++;
                     mst += e[i].w;
                 }
             }
             printf("%d %d\n",ne,mst);
        }
     }
     return 0;
 }