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 rep(i,n) for(int i=0;i<(int)(n);++i)
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define ALL(a) (a).begin(),(a).end()
#define SZ(a) (int)((a).size())
typedef long long ll;
typedef pair<int,int> PI;

vector<PI> ed[11000];

vector<int> G[510];
int low[510];
int num[510];
int lownum;
bool isart[510];

void lowdfs(int v){
  num[v] = low[v] = lownum++;
  
  for(auto e : G[v]){
    if(low[e] == -1){
      lowdfs(e);
      low[v] = min(low[v], low[e]);
      isart[v] |=
        (num[v]==0 && num[e] != 1)||
        (num[v]!=0 && low[e] >= num[v]);
    }else low[v] = min(low[v], num[e]);
  }
}

void visit(int v,int u,vector<PI>&brdg,stack<int>&roots,stack<int>&S,vector<bool>&inS,
           vector<int>&num,int&time){
  num[v] = ++time;
  S.push(v);
  inS[v]=true;
  roots.push(v);
  for(auto e : G[v]){
    int w = e;
    if(num[w] == 0)
      visit(w,v,brdg,roots,S,inS,num,time);
    else if(u != w && inS[w])
      while(num[roots.top()] > num[w]) roots.pop();
  }

  if(v == roots.top()){
    brdg.push_back(mp(u,v));
    while(1){
      int w = S.top();S.pop();inS[w] = false;
      if(v==w) break;
    }
    roots.pop();
  }
}

vector<PI> bridge(){
  vector<int> num(510);
  vector<bool> inS(510);
  stack<int> roots,S;
  int time = 0;
  vector<PI> brd;
  
  rep(u,510) if(num[u]==0){
    visit(u,500,brd,roots,S,inS,num,time);
    brd.pop_back();
  }
  return brd;
}

int un[510];
int find(int x){
  if(un[x] == x) return x;
  return un[x] = find(un[x]);
}

void unit(int a,int b){
  un[find(a)] = find(b);
}


int solve(int cc){
  if(ed[cc].empty()) return 0;
  lownum = 0;
  //rep(i,500) G[i].clear();
  set<PI> ap;
  for(auto e : ed[cc]){
    G[e.F].pb(e.S);
    G[e.S].pb(e.F);
    ap.insert(e);
    ap.insert(mp(e.S,e.F));
  }
  
  // rep(i,500) low[i] = -1;
  // rep(i,500) isart[i] = 0;
  // rep(i,500){
  //   if(low[i] == -1) lowdfs(i);
  // }
  auto br = bridge();
  int ou = 0;
  for(auto e : br){
    
    ou += find(e.F) != find(e.S) &&
      ap.count(mp(e.F,e.S));
  }
  
  //cout << ou << " " << br.size() << endl;
  return ou;
  return br.size();
  // vector<PI> ed = bridge();
  


  // // rep(i,4) cout << isart[i] << " ";
  // // cout << endl;
  
  // for(auto e : ed[cc])
  //   use += isart[e.F] && isart[e.S];
  
  // return use;
}

int main(int argc, char *argv[])
{
  int n,m;
  cin >> n >> m;
  rep(i,n) un[i] = i;
  rep(i,m){
    int a,b,c;

    cin >> a >> b >> c;
    --a,--b;
    ed[c].pb(mp(a,b));
  }
  
  int ans = 0;
  ll acost = 0;
  for(int i = 1; i <= 10000;++i){
    int nu = solve(i);
    for(auto e : ed[i]) unit(e.F,e.S);
    ans += nu;
    acost += nu*i;
  }
  
  cout << ans << " " << acost << endl;
}