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>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 //...
struct Edge { 
  int src,dst,w; 
  bool operator < ( const Edge& e ) const {
    if( w != e.w ) return w < e.w;
    if( src != e.src ) return src < e.src;
    return dst < e.dst;
  }
};
const int MAX_V = 510; //
int V,E; //
vector<Edge> G[MAX_V]; // undirected graph
vector<int> dfs_num,dfs_low,dfs_parent,articulation_vertex;
int dfsNumberCounter, dfsRoot, rootChildren;
int cost[MAX_V][MAX_V];
 
//O(V+E)
int base_weight;
vector<Edge> bridges;
#define UNVISITED -1
void articulationPointAndBridge(int u){
  dfs_low[u] = dfs_num[u] = dfsNumberCounter++;
  rep(j,(int)G[u].size()){
    Edge &v = G[u][j];
    if( dfs_num[v.dst] == UNVISITED ) {
      dfs_parent[v.dst] = u;
      if( u == dfsRoot ) rootChildren++;
 
      articulationPointAndBridge(v.dst);
 
      if( dfs_low[v.dst] >= dfs_num[u] ) articulation_vertex[u] = true;
      if( dfs_low[v.dst] >  dfs_num[u] ) {
        if( base_weight == cost[u][v.dst] ) {
          bridges.push_back((Edge){u,v.dst,base_weight});
        }
        //printf("Edge (%d,%d) is a bridge\n",u,v.dst);
      }
      dfs_low[u] = min(dfs_low[u],dfs_low[v.dst]);
    } else if( v.dst != dfs_parent[u] ) {
      dfs_low[u] = min(dfs_low[u],dfs_num[v.dst]);
    }
  }
}
 
void calculateArticulationPointAndBridge(){
  dfsNumberCounter = 0;
  dfs_num.assign(V,UNVISITED);
  dfs_low.assign(V,0);
  dfs_parent.assign(V,0);
  articulation_vertex.assign(V,0);
   
  rep(i,V) {
    if( dfs_num[i] == UNVISITED ) {
      dfsRoot = i, rootChildren = 0;
      articulationPointAndBridge(i);
      articulation_vertex[dfsRoot] = ( rootChildren > 1 );
    }
  }
}
 
int par[MAX_V];
 
int find(int x){
  if( x == par[x] ) return x;
  return par[x] = find(par[x]);
}
 
void unit(int x,int y){
  x = find(x), y = find(y);
  if( x != y ) par[x] = y;
}
 
 
void compute(vector<Edge> edges){
  set<int> weights;
  rep(i,V) par[i] = i;
  sort(edges.begin(),edges.end());
  rep(i,E){
    Edge &e = edges[i];
    if( find(e.src) != find(e.dst) ) {
      unit(e.src,e.dst);
      weights.insert(e.w);
    }
  }
  int cnt=0,sum=0;
  int cur = 0;
  for(set<int>::iterator it=weights.begin();it!=weights.end();it++){
    int w = *it;
    while( cur < E && edges[cur].w < w ) ++cur;
    if( cur >= E ) break;
    if( edges[cur].w > w ) continue;
    base_weight = w;
    while( cur < E && edges[cur].w == w ) {
      Edge &e = edges[cur++];
      G[e.src].push_back((Edge){e.src,e.dst,e.w});
      G[e.dst].push_back((Edge){e.dst,e.src,e.w});
    }
    bridges.clear();
    calculateArticulationPointAndBridge();
    cnt += (int)bridges.size();
    sum += (int)bridges.size() * w;
  }
  printf("%d %d\n",cnt,sum);
}
 
int main(){
  memset(cost,-1,sizeof(cost));
  vector<Edge> edges;
  scanf("%d %d",&V,&E);
  {
    int s,t,w;
    rep(i,E){
      scanf(" %d %d %d",&s,&t,&w);
      --s, --t;
      edges.push_back((Edge){s,t,w});
      cost[s][t] = cost[t][s] = w;
    }
  }
  compute(edges);
  return 0;
}