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<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
struct node
{
    int id,u,v,cost,next;
    bool vis;
}edge[100010],arr[50010];
int T,t,n,m;
int p[50010],Head[510],tot,tot2,tot3,tot4,ans1,ans2;
int vis[510],U[510];
int stack[510],DFN[510],Low[510],Belong[510];
bool instack[510];
int top,cnt,scnt;
bool cmp(node a,node b)
{
    return a.cost<b.cost;
}
int find(int x)
{
    return p[x]==x ? x : p[x]=find(p[x]);
}
void _add(int u)
{
    if(vis[u]!=t)
    {
        vis[u]=t;
        U[++U[0]]=u;
    }
}
void add(int u,int v,int cost)
{
    //printf("%d %d %d\n",u,v,cost);
    edge[tot2].u=u;
    edge[tot2].v=v;
    edge[tot2].next=Head[u];
    edge[tot2].vis=0;
    Head[u]=tot2++;
}
void Tarjan(int u)
{
    //printf("Tarjan %d\n",u);
    int i,j,k,v;
    DFN[u]=Low[u]=++tot4;
    instack[u]=1;
    stack[top++]=u;
    for(i=Head[u];i>=tot;i=edge[i].next)
    {
        v=edge[i].v;
        if(edge[i].vis==1)
          continue;
        edge[i].vis=edge[i^1].vis=1;
        if(DFN[v]<=tot3)
        {
            Tarjan(v);
            Low[u]=min(Low[u],Low[v]);
        }
        else if(instack[v])
          Low[u]=min(Low[u],DFN[v]);
    }
    if(DFN[u]==Low[u])
    {
        scnt++;
        do
        {
            v=stack[--top];
            instack[v]=0;
            Belong[v]=scnt;
        }while(u!=v);
    }
}
int main()
{
    int i,j,k,l,r,u,v;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&arr[i].u,&arr[i].v,&arr[i].cost);
        arr[i].id=i;
    }
    for(i=1;i<=n;i++)
       p[i]=i;
    memset(Head,-1,sizeof(Head));
    sort(arr+1,arr+1+m,cmp);
    l=r=1;
    while(r<=m)
    {
        while(r<m && arr[r+1].cost==arr[r].cost)
          r++;
        tot=tot2;
        t++;
        U[0]=0;
        for(i=l;i<=r;i++)
        {
            u=find(arr[i].u);
            v=find(arr[i].v);
            if(u==v)
              continue;
            _add(v);_add(u);
            add(u,v,arr[i].cost);
            add(v,u,arr[i].cost);
        }
        tot3=tot4;
        top=cnt=scnt=0;
        for(i=1;i<=U[0];i++)
           if(DFN[U[i]]<=tot3)
             Tarjan(U[i]);
        //for(i=1;i<=U[0];i++)
        //   printf("Belong %d\n",Belong[U[i]]);
        for(i=l;i<=r;i++)
           if(Belong[find(arr[i].u)]!=Belong[find(arr[i].v)])
           {
               ans1++;
               ans2+=arr[i].cost;
           }

        for(i=l;i<=r;i++)
        {
            u=find(arr[i].u);
            v=find(arr[i].v);
            if(u==v)
              continue;
            p[v]=u;
        }
        l=r=r+1;
    }
    printf("%d %d\n",ans1,ans2);
}