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;
#define FOR(i,bg,ed) for(int i=bg;i<ed;i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) v.begin(),v.end()


typedef long long LL;
typedef double D;

namespace _DSU{
    int cnt = 0;
    int mem[2][212345];
    int *get(){
        return mem[cnt++];
    }
}
struct UF{
    int *par,*rank;
    int find(int x){
        if(par[x]==x)return x;
        else return par[x]=find(par[x]);
    }
    UF(int n){
        par  = _DSU::get();
        rank  = _DSU::get();
        REP(i,n){
            par[i]=i;
            rank[i]=0;
        }
    }
    bool unite(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y)return false;
        if(rank[x]<rank[y])par[x]=y;
        else{
            par[y]=x;
            if(rank[x]==rank[y])rank[x]++;
        }
        return true;
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
};

typedef vector<int> V;
typedef vector<V> VV;
int a[51234];
int b[51234];
int c[51234];
int f(int v,VV &g,V &used,V &cnt,V& depth,int pe=-1){
    int ret=0;
    used[v]=1;

    for(auto &e:g[v]){
        if(e==pe)continue;
        int u=v^a[e]^b[e];
        if(used[u]){
            if(depth[u]<depth[v]){
                cnt[v]++;
                cnt[u]--;
            }
        }
        else {
            depth[u]=depth[v]+1;
            ret+=f(u,g,used,cnt,depth,e);
            cnt[v]+=cnt[u];
        }
    }
    if(cnt[v]==0) ret++;
    return ret;
}

LL count(VV g){
    int N=g.size();
    V used(N,0);
    V cnt(N,0);
    V depth(N,0);
    int ans=0;
    REP(i,N)if(!used[i]){
        ans+=f(i,g,used,cnt,depth)-1;
    }
    return ans;
}
#define fi first
#define se second
#define pb push_back
#define P pair
int main(){
    int n,m;
    cin>>n>>m;
    vector<P<int,int>> edge(m);
    REP(i,m){
        cin>>a[i]>>b[i]>>c[i];
        a[i]--;
        b[i]--;
        edge[i]={c[i],i};
    }
    sort(ALL(edge));
    UF uf(n);
    LL r1=0;
    LL r2=0;
    REP(i,m){
        int bg=i;
        int ed=i;
        while(ed+1<=m&&c[edge[bg].se]==c[edge[ed+1].se])
            ed++;
        VV g(n);
        FOR(j,bg,ed+1){
            int e = edge[j].se;
            a[e]=uf.find(a[e]);
            b[e]=uf.find(b[e]);

            int s=a[e];
            int t=b[e];

            if(!uf.same(s,t)){
                g[uf.find(s)].pb(e);
                g[t].pb(e);
            }
        }
        LL k = count(g);
        r1+=k;
        r2+=c[edge[bg].se]*k;
        FOR(j,bg,ed+1){
            int e = edge[j].se;
            uf.unite(a[e],b[e]);
        }
        i=ed;
    }
    cout<<r1<<" "<<r2<<endl;
    return 0;
}