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;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)
typedef long long int i64;
typedef pair<int, int> pint;

struct UnionFind {
    vector<int> data; int group;
    UnionFind(int N) : data(N, -1), group(N) {}
    void init(int N) {
        data.assign(N, -1);
        group = N;
    }
    void unite(int x, int y) {
        x = root(x); y = root(y);
        if(x != y){
            data[x] += data[y];
            data[y] = x;
            --group;
        }
    }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]);}
    bool same(int a, int b) { return root(a) == root(b);}
};

struct Edge {
    int from, to, num;
    Edge(int f, int t, int n)
         : from(f), to(t), num(n) {}
};
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N, M; cin >> N >> M;
    int s_, t_, c_;
    map<int, vector<Edge>> edges;
    rep(i, M) {
        cin >> s_ >> t_ >> c_;
        --s_; --t_;
        edges[c_].push_back(Edge(s_, t_, i));
    }
    UnionFind uf(N);
    vector<pint> memo;
    for(const auto& pev: edges) { 
        rep(i, pev.second.size()) {
            Edge e = pev.second[i];
            if(uf.same(e.from, e.to)) continue;
            uf.unite(e.from, e.to);
            memo.push_back(pint(pev.first, i));
        }
    }
    int ans_num = 0, ans_cos = 0;
    for(const pint& p : memo) {
        Edge aim = edges[p.first][p.second];
        UnionFind temp(N);
        for(const pint& e : memo)
          if(p != e) temp.unite(edges[e.first][e.second].from, edges[e.first][e.second].to);
        int ra = temp.root(aim.from), rb = temp.root(aim.to);
        bool ok = true;
        REP(i, p.second + 1, edges[p.first].size()) {
            Edge e = edges[p.first][i];
            int rf = temp.root(e.from), rt = temp.root(e.to);
            if((ra == rf && rb == rt) || (ra == rt && rb == rf)) {
                ok = false;
                continue;
            }
        }
        if(ok) { ans_num++; ans_cos += p.first;}
    }
    cout << ans_num << ' ' << ans_cos << endl;
    return 0;
}