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"

struct Edge {
  int src, dst;
  long long weight;
  Edge(int src, int dst, long long weight)
      : src(src), dst(dst), weight(weight) {}

  bool operator<(const Edge &e) const { return weight > e.weight; }
};

using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;

std::pair<long long, Edges> Prim(const Graph &g, int s) {
  int n = g.size();
  Edges tree;
  long long total = 0;
  std::vector<int> visited(n, 0);
  std::priority_queue<Edge> q;
  q.emplace(-1, s, 0);
  while (!q.empty()) {
    Edge e = q.top();
    q.pop();
    if (visited[e.dst])
      continue;
    if (e.src != -1)
      tree.push_back(e);
    total += e.weight;
    visited[e.dst] = true;
    for (auto f : g[e.dst]) {
      if (!visited[f.dst])
        q.push(f);
    }
  }
  return std::pair<long long, Edges>(total, tree);
}

constexpr long long INF64 = 1e18;

using Weight = long long;

using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
//経路復元可能
Weight Dijkstra(const Graph &g, int s, int t) {
  const int V = g.size();
  std::vector<Weight> dist(V, INF64);
  std::vector<int> prev(V, -1);
  std::priority_queue<Edge> q;
  dist[s] = 0;
  for (q.emplace(-2, s, 0); !q.empty();) {
    Edge e = q.top();
    q.pop();
    if (prev[e.dst] != -1)
      continue;
    prev[e.dst] = e.src;
    if (prev[t] != -1)
      return dist[t];
    for (auto ge : g[e.dst]) {
      if (dist[ge.dst] > e.weight + ge.weight) {
        dist[ge.dst] = e.weight + ge.weight;
        q.emplace(ge.src, ge.dst, e.weight + ge.weight);
      }
    }
  }
  return dist[t];
}

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  Graph g(n);
  for (int i = 0; i < m; ++i) {
    int s, t;
    long long c;
    cin >> s >> t >> c;
    s--;
    t--;
    g[s].push_back({s, t, c});
    g[t].push_back({t, s, c});
  }
  Graph tree(n);
  auto prim = Prim(g, 0);
  auto edges = prim.second;
  for (const auto &e : edges) {
    tree[e.src].push_back({e.src, e.dst, e.weight});
  }
  long long ans = 0;
  int count = 0;
  {
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
      int p = q.front();
      q.pop();
      for (const auto &e : tree[p]) {
        Graph gg(n);
        for (const auto &ges : g) {
          for (const auto &gee : ges) {
            if (gee.src == e.dst and gee.dst == e.src)
              continue;
            gg[gee.src].push_back(gee);
          }
        }
        if (prim.first != Prim(gg, e.dst).first) {
          ans += e.weight;
          count++;
        }
        q.push(e.dst);
      }
    }
  }
  cout << count << " " << ans << endl;
}