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;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<n;i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

namespace Bridge{
    vector<int> ord,low;
    vector<pair<int,int>> res;
    int count=0;

    // O(n+m)
    int dfs(int cur,int parent,const vector<vector<int>> &G){
        ord[cur] = count++;
        low[cur] = ord[cur];
        for(int to : G[cur]){
            if(to == parent){
                continue;
            }else if(ord[to] != -1){
                low[cur] = min(low[cur],low[to]);
            }else{
                low[cur] = min(low[cur],dfs(to,cur,G));
                if(ord[cur] < low[to]){
                    res.push_back(make_pair(cur,to));
                }
            }
        }
        return low[cur];
    }

    vector<pair<int,int>> detect_from_tree(const vector<vector<int>> &g){
        ord.assign(g.size(),-1);
        low.assign(g.size(),-1);
        count = 0;
        dfs(0,-1,g);
        return res;
    }

    vector<pair<int,int>> detect_from_forest(const vector<vector<int>> &g){
        ord.assign(g.size(),-1);
        low.assign(g.size(),-1);
        count = 0;
        for(int i=0;i<g.size();i++){
            if(ord[i]==-1){
                dfs(i,-1,g);
            }
        }
        return res;
    }
};

int main(){
    int N,M;
    cin >> N >> M;
    vector<pair<int,pair<int,int>>> G;
    map<int,vector<pii>> a;
    map<pair<int,int>,int> tmp;
    rep(i,M){
        int s,d,c; cin >> s >> d >> c;
        s--;
        d--;
        G.push_back(mp(c,mp(s,d)));
        a[c].push_back(mp(s,d));
        tmp[mp(s,d)] = c;
        tmp[mp(d,s)] = c;
    }
    sort(all(G));

    int ans_edge = 0;
    int ans_cost = 0;
    vector<vector<int>> G2(N);
    for(const auto& p : a){
        int cost = p.first;
        const vector<pii> &vec = p.second;
        for(pii uv : vec){
            int u = uv.first;
            int v = uv.second;
            G2[u].push_back(v);
            G2[v].push_back(u);
        }
        vector<pii> b = Bridge::detect_from_forest(G2);
        int cnt = 0;
        for(pii e : b){
            if(tmp[e] == cost) cnt++;
        }
        ans_edge += cnt;
        ans_cost += cnt * cost;
    }
    cout << ans_edge << " " << ans_cost << endl;
}