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 Dsu {
  struct node_struct {
    int par, size;
    node_struct(int p, int s) : par(p), size(s) {}
    void merge(node_struct &b) {
      b.par = par;
      size += b.size;
    }
  };
  vector<node_struct> nodes;
  stack<tuple<int, int, node_struct, node_struct>> stk;
  Dsu(int n) {
    nodes.reserve(n);
    for (int i = 0; i < n; ++i) nodes.emplace_back(i, 1);
  }
  int anc(int x) {
    while (x != nodes[x].par) x = nodes[x].par;
    return x;
  }
  bool unite(int x, int y) {
    int a = anc(x);
    int b = anc(y);
    stk.emplace(a, b, nodes[a], nodes[b]);
    if (a == b) return false;
    if (nodes[a].size < nodes[b].size) swap(a, b);
    nodes[a].merge(nodes[b]);
    return true;
  }
  void revert(int version = -1) {  // 0 index
    if (version == -1) version = stk.size() - 1;
    for (; stk.size() != version; stk.pop()) {
      nodes[get<0>(stk.top())] = get<2>(stk.top());
      nodes[get<1>(stk.top())] = get<3>(stk.top());
    }
  }
};


vector<tuple<int, int, int, int>> E;

vector<vector<pair<int, int>>> g;


int ans[1<<17], pa[1<<17], paid[1<<17];
int tin[1<<17], tout[1<<17];

void dfs(int u, int p) {
  static int cur = 0;
  tin[u] = cur++;
  for (auto P : g[u]) {
    int v, i; tie(v, i) = P;
    if (v == p) continue;
    pa[v] = u, paid[v] = i;
    dfs(v, u);
  }
  tout[u] = cur;
}
 

bool anc(int u, int p) {
  return tin[p] <= tin[u] and tout[u] <= tout[p];
}
  

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, m; cin >> n >> m;
  fill(ans, ans + m, INT_MAX);
  g.resize(n);
  for (int i = 0; i < m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    --u, --v;
    E.emplace_back(w, v, u, i);
  }
  sort(E.begin(), E.end());
  Dsu djs(n);
  for (auto T : E) {
    int u, v, w, i;
    tie(w, u, v, i) = T;
    if (djs.unite(u, v)) {
      g[u].emplace_back(v, i);
      g[v].emplace_back(u, i);
    }
    else ans[i] = w;
  }
  dfs(0, 0);
  for (auto T : E) {
    int u, v, w, i; tie(w, u, v, i) = T;
    if (pa[u] == v or pa[v] == u) continue;
    for (int _ = 0; _ < 2; ++_, swap(u, v)) {
      while (not anc(u, v)) {
        ans[paid[v]] = min(ans[paid[v]], w);
        v = pa[v];
      }
    }
  }
  int ansnum = 0, answ = 0;
  for (auto T : E) {
    int u, v, w, i; tie(w, u, v, i) = T;
    if (ans[i] > w) ++ansnum, answ += w;
  }
  cout << ansnum << ' ' << answ << '\n';
}