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;
#define INF 10000000

set<pair<int, int> > s;
int x = -1, y = -1;
int tmp;

int prim(int v, vector<vector<pair<int, int> > > adjlist){

    priority_queue<pair<int, pair<int, int> > > wait;    // first := 候補辺のコスト   second　:= {from, to}
    vector<int> result(v, INF);               // 頂点iと木の間の最小コスト
    int ans = 0, size = 0;                    // 木のコスト　頂点数

    //初期条件
    result[0] = 0;
    wait.push({0, {-1, 0}});

    while(!wait.empty() && size < v){

        //候補辺のうち最小のものを取り出す
        int from = wait.top().second.first;
        int newpoint = wait.top().second.second;
        int newcost = -wait.top().first;
        if(from != -1 && x == -1) s.insert({from, newpoint});
        wait.pop();
        //cout << x + 1 << " " << y + 1 << " " << from + 1 << " " << newpoint + 1 << endl;


        if(result[newpoint] < newcost) continue;

        //出てきた頂点を木に追加
        ans += newcost;
        result[newpoint] = -INF;
        size++;

        // 新しい点から出ている辺をすべてなめる
        for(int i = 0; i < adjlist[newpoint].size(); i++){
            int nextpoint = adjlist[newpoint][i].second;
            int nextcost = adjlist[newpoint][i].first;
            
            if((x == nextpoint && y == newpoint) || (x == newpoint && y == nextpoint)){
                //cout << "ok" << endl;
                tmp = nextcost;
                //cout << tmp << endl;
                continue;
            }
            
            //より木に近くなった頂点があれば,　そこへの枝をqueueに追加
            if(result[nextpoint] > nextcost){
                result[nextpoint] = nextcost;
                wait.push({-nextcost, {newpoint, nextpoint}});
            }
        }
    }

    return ans;
}



int main(){

    int V, E; cin >> V >> E;                          // V:= 頂点の数    E:= 辺の数 
    vector<vector<pair<int, int> > > adjlist(V);      //first := コスト　second := 行先

    //入力
    for(int i = 0; i < E; i++){
        int a, b, c; cin >> a >> b >> c;              // a ,b 間に コスト c の辺がある
        a--; b--;
        adjlist[a].push_back(make_pair(c, b));
        adjlist[b].push_back(make_pair(c, a));      
    }

    int ans = prim(V, adjlist);
    //cout << ans << endl;
    int num = 0;
    int cost = 0;
    for(auto e : s){
        //cout << e.first + 1 << " " << e.second + 1 << endl;
        x = e.first;
        y = e.second;
        int w = prim(V, adjlist);
        //cout << "remove " << x + 1 << " " << y + 1 << " : w = " << w << endl;
        if(ans != w){
            //cout << u + 1 << " " << v + 1 << endl;
            //cout << "addcost " << tmp << endl;
            num++;
            cost += tmp;
        }
    }

    cout << num << " " << cost << endl;
    
    return 0;
}