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;

struct Edge{
    int s,d;
};
using Graph=vector<vector<int>>;
map<pair<int,int>,int> mp2;
int cntBridge(const Graph& g){
    int n=g.size();
    vector<int> pre(n,-1),low(n,-1);
    int k=0;
    int res=0;
    int root=0;
    function<int(int,int)> dfs=[&](int v,int pv){
        if(pre[v]!=-1) return low[v];
        pre[v]=k++;
        low[v]=pre[v];
        for(auto &to:g[v]){
            if(to!=pv){
                if(pre[to]==-1){
                    low[v]=min(low[v],dfs(to,v));
                    if(low[to]==pre[to] && to!=root){
                        if(mp2[{v,to}]==1){
                            res++;
                            //cerr<<v<<" "<<to<<endl;
                        }
                    }
                }
                else{
                    low[v]=min(low[v],dfs(to,v));
                }
            }
        }
        return low[v];
    };
    vector<int> f(n,0);
    for(int i=0;i<n;i++){
        if(pre[i]==-1){
            root=i;
            dfs(i,-1);
            f[i]=1;
        }
    }
    return res;
}
int main(){
    int n,m;
    cin>>n>>m;
    map<int,vector<Edge>> mp;
    for(int i=0;i<m;i++){
        int s,d,c;
        cin>>s>>d>>c;
        s--,d--;
        mp[c].push_back({s,d});
    }    
    Graph g(n);
    int cnt=0;
    int sum=0;

    vector<int> rank(n);
    vector<int> par(n);
    iota(par.begin(),par.end(),0);
    function<int(int)> find=[&](int x){
        if(par[x]==x) return x;
        else return par[x]=find(par[x]);
    };
    auto unite=[&](int x,int y){
        x=find(x),y=find(y);
        if(x==y) return;
        if(rank[x]<rank[y]) par[x]=y;
        else{
            if(rank[x]==rank[y]) rank[x]++;
            par[y]=x;
        }
    };

    for(auto &e:mp){
        int c=e.first;
        vector<Edge> edges=e.second;
        Graph g(n);
        for(auto &e:edges){
            int x=find(e.s),y=find(e.d);
            if(x==y) continue;
            //cerr<<"#"<<x<<" "<<y<<endl;
            mp2[{x,y}]++;
            mp2[{y,x}]++;
            //cerr<<mp2[{x,y}]<<endl;
            //cerr<<mp2[{y,x}]<<endl;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        int x=cntBridge(g);
        cnt+=x;
        sum+=x*c;
        for(auto &e:edges) unite(e.s,e.d);
    }
    cout<<cnt<<" "<<sum<<endl;
    return 0;
}