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 <iostream>
#include <cassert>
#include <cstring>
#include <algorithm>
#include <vector>
 
using namespace std;
#define whole(xs) (xs).begin(),(xs.end())
 
int N, M;
 
struct Edge {
    int from, to, cost;
    Edge(int from, int to, int cost) :
        from(from), to(to), cost(cost) {}
    bool operator==(const Edge& e) const {
        return from == e.from &&
            to == e.to &&
            cost == e.cost;
    }
};
 
struct UnionFind {
    vector<int> parent;
    int N;
    UnionFind(int N) : N(N) {
        parent.resize(N);
        fill(whole(parent), -1);
    }
    int root(int x) {
        if (parent[x] == -1) return x;
        return parent[x] = root(parent[x]);
    }
    int query(int x, int y) {
        return root(x) == root(y);
    }
    void merge(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        parent[y] = x;
    }
};
 
bool EdgeComp(const Edge& a, const Edge& b) {
    return a.cost < b.cost;
}

#define MN 503
 
int Count, Cost;
bool used[MN][MN];
int L[MN][MN];
bool dfs(vector< vector<Edge> >& G, int u, int v, int cost, vector<int>& prev) {
    //cout << "u, v = " << u << " " << v << endl;
    //cout << "prev[v]: " << prev[v] << endl;
    if (prev[v] == 0) {
        int a = v, b = u;
        do {
            //cout << "a, b: " << a << " " << b << endl;
            if (!used[a][b] && !used[b][a] && L[a][b] == cost) {
                //cout << "a, b = " << a << " " << b << endl;
                used[a][b] = true;
                used[b][a] = true;
                Count--;
                Cost -= L[a][b];
            }
            a = b;
            b = prev[b];
        } while (a != v);
        return true;
    }
    prev[v] = u;
    for (int i = 0; i < G[v].size(); i++) {
        Edge& e = G[v][i];
        if (e.to == u) continue;
        if (dfs(G, v, e.to, e.cost, prev)) return true;
    }
    return false;
}
 
int main() {
    cin >> N >> M;
    vector<Edge> es;
    memset(L, 0, sizeof(L));
    for (int i = 0; i < M; i++) {
        int s, d, c;
        cin >> s >> d >> c;
        L[s][d] = c;
        L[d][s] = c;
        es.push_back(Edge(s, d, c));
    }
    vector< vector<Edge> > G(N + 1);
    Count = 0;
    Cost = 0;
    UnionFind uf(N + 1);
    sort(whole(es), EdgeComp);
    memset(used, false, sizeof(used));
    for (int i = 0; i < M; i++) {
        //cout << "\t" << Count << " " << Cost << endl;
        Edge& e = es[i];
        if (uf.query(e.from, e.to)) {
            G[e.from].push_back(Edge(e.from, e.to, e.cost));
            G[e.to].push_back(Edge(e.to, e.from, e.cost));
            Cost += e.cost;
            Count++;
            vector<int> prev(N + 1, -1);
            dfs(G, 0, e.from, e.cost, prev);
            G[e.from].pop_back();
            G[e.to].pop_back();
        } else {
            uf.merge(e.from, e.to);
            G[e.from].push_back(Edge(e.from, e.to, e.cost));
            G[e.to].push_back(Edge(e.to, e.from, e.cost));
            Cost += e.cost;
            Count++;
        }
    }
    cout << Count << " " << Cost << endl;
    return 0;
}