Problem: Example

Input

4 4
1 2 3
1 3 3
2 3 3
2 4 3


Output

1 3

Solution (in CPP):

Solution:
// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

class range {
    struct Iterator {
        int val, inc;
        int operator*() {return val;}
        bool operator!=(Iterator& rhs) {return val < rhs.val;}
        void operator++() {val += inc;}
    };
    Iterator i, n;
    public:
    range(int e) : i({0, 1}), n({e, 1}) {}
    range(int b, int e) : i({b, 1}), n({e, 1}) {}
    range(int b, int e, int inc) : i({b, inc}), n({e, inc}) {}
    Iterator& begin() {return i;}
    Iterator& end() {return n;}
};

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

typedef vector<int> Node;
typedef vector<Node> Graph;
class ArticulationPoint {
    vector<int> ord, low, art;
    int cnt;
    vector<pair<int, int> > _bridges;
    void dfs(const Graph&G, int v, int p) {
        ord[v] = low[v] = cnt++;
        for(int i = 0; i < G[v].size(); i++) {
            int w = G[v][i];
            if(ord[w] == -1) {
                dfs(G, w, v);
                low[v] = min(low[v], low[w]);
                if(ord[v] <= low[w]) art[v]++;
                if(ord[v] <  low[w]) _bridges.push_back(make_pair(min(v, w), max(v, w)));
            } else if(w != p) {
                low[v] = min(low[v], ord[w]);
            }
        }
    }

public:
    // Time complexity: O(V + E)
    ArticulationPoint(const Graph& G) {
        int n = G.size();
        cnt = 0;
        ord.assign(n, -1);
        low.assign(n, 0);
        art.assign(n, 0);
        for(int i = 0; i < n; i++) {
            if(ord[i] == -1) {
                dfs(G, i, -1);
                if (art[i]) art[i]--;
            }
        }
    }

    // return whether (v, w) is a bridge or not.
    bool is_bridge(int v, int w) { return ord[v] < low[w] || ord[w] < low[v]; }

    // return all bridges.
    const vector<pair<int, int>>& bridges() { return _bridges; }

    // return whether v is a articulation point or not.
    bool is_art(int v) { return art[v] > 0; }

    // return how many number of connected components are increased if we remove a vertex v.
    int inc_CC(int v) { return art[v]; }
};
int main(){
    iostream_init();
    int N, M;
    while(cin >> N >> M) {
        const int MAX_C = 100000 + 1;
        vector<pair<int, int>> edges[MAX_C];
        REP(i, M) {
            int a, b, c;
            cin >> a >> b >> c;
            a--; b--;
            edges[c].emplace_back(a, b);
        }

        int cnt = 0;
        long long sum = 0;
        Graph G(N);
        REP(c, MAX_C) if(edges[c].size() > 0) {
            for(auto p : edges[c]) {
                G[p.first].push_back(p.second);
                G[p.second].push_back(p.first);
            }
            ArticulationPoint ap(G);
            for(auto p : edges[c]) {
                if(ap.is_bridge(p.first, p.second)) {
                    cnt++;
                    sum += c;
                }
            }
        }
        cout << cnt << " " << sum << endl;
    }

    return 0;
}

/* vim:set foldmethod=marker: */