Untitled

// AC(6/6) 2700ms
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

// To represent Disjoint Sets 
struct DisjointSets{ 
    int *parent, *rnk; 
    int n; 
  
    // Constructor. 
    DisjointSets(int n){ 
        // Allocate memory 
        this->n = n; 
        parent = new int[n+1]; 
        rnk = new int[n+1]; 
  
        // Initially, all vertices are in 
        // different sets and have rank 0. 
        for (int i = 0; i <= n; i++){ 
            rnk[i] = 0; 
  
            //every element is parent of itself 
            parent[i] = i; 
        } 
    } 
  
    // Find the parent of a node 'u' 
    // Path Compression 
    int find(int u){ 
        /* Make the parent of the nodes in the path 
        from u--> parent[u] point to parent[u] */
        if (u != parent[u]) 
            parent[u] = find(parent[u]); 
        return parent[u]; 
    } 
  
    // Union by rank 
    void merge(int x, int y){ 
        x = find(x), y = find(y); 
  
        /* Make tree with smaller height 
        a subtree of the other tree */
        if (rnk[x] > rnk[y]) 
            parent[y] = x; 
        else // If rnk[x] <= rnk[y] 
            parent[x] = y; 
  
        if (rnk[x] == rnk[y]) 
            rnk[y]++; 
    } 
};

class edge{  //自製的容器，用來表達edge
    public:
        edge():s(0),e(0),cost(0){}
        edge(int s,int e,int cost):s(s),e(e),cost(cost){}
        int s;
        int e;
        int cost;
        bool operator<(const edge &B) const{  //for the purpose of reverse sorting
            return cost < B.cost;
        }
        bool operator==(const edge &B) const{
            return (B.s == s) && (B.e == e) && (B.cost == cost);
        }
};

int N;
int E;
long long Cost = LLONG_MAX;
vector<edge> graph;

long long MST_select(edge A,DisjointSets &ds){  //開場先挑A edge
    long long cost = 0;

    int u = A.s,v = A.e;

    int set_u = ds.find(u); 
    int set_v = ds.find(v);
    ds.merge(set_u, set_v); 
    cost += A.cost;


    for(auto &a:graph){

        if(E == N-1) break;
        if(a==A) continue;
        if(cost > Cost) break;

        int u = a.s,v = a.e;

        int set_u = ds.find(u); 
        int set_v = ds.find(v); 

        if (set_u != set_v) { 
            // Merge two sets 
            ds.merge(set_u, set_v); 
            cost += a.cost;
        }
    }

    // re-initialize，為了下一把還能重複使用Disjoint set，幫它重新初始化一下
    for (int i = 0; i <= N; i++) { 
        ds.rnk[i] = 0; 
        //every element is parent of itself 
        ds.parent[i] = i; 
    }
    
    return cost;
}

long long MST_skip(edge A,DisjointSets &ds){   //必略過A edge不挑
    long long cost = 0;

    for(auto &a:graph){

        if(E == N-1) break;
        if(a==A) continue;
        if(cost > Cost) break;

        int u = a.s,v = a.e;

        int set_u = ds.find(u); 
        int set_v = ds.find(v); 

        if (set_u != set_v) { 
            // Merge two sets 
            ds.merge(set_u, set_v); 

            cost+=a.cost;
        }
    }

    // re-initialize，為了下一把還能重複使用Disjoint set，幫它重新初始化一下
    for (int i = 0; i <= N; i++) { 
        ds.rnk[i] = 0; 
        //every element is parent of itself 
        ds.parent[i] = i; 
    }
    
    return cost;
}


int main(){
    std::ios::sync_with_stdio(false);

    cin >> N;
    cin >> E;
    for(int i=0;i<E;i++){  //輸入所有的邊
        int s,e,c;
        cin >> s >> e >> c;
        graph.push_back(edge(s,e,c));
    }

    sort(graph.begin(),graph.end());  //把所有的邊依照cost作升序排列

    DisjointSets ds(N);  //建立一個Disjoint set，為了在Kruscal中O(logN) detect cycle (要很客家的重複使用，不然要吃MLE)

    Cost = MST_skip(edge(),ds);    //找到一般的，MST的cost
    int essential_cnt = 0,secondary_cnt = 0;


    /*對每條邊進行考慮
    拿掉這條邊就造不出MST(cost > min_cost，Kruscal失敗) -> 這條邊存在於所有MST (essential link)
    造得出包含這條邊的MST(cost == min_cost，Kruscal成功) -> 這條邊存在於某些(有可能全部)MST中 (至少也是secondary link)*/
    for(auto &a:graph){
        if(MST_skip(a,ds) > Cost) essential_cnt++;
        else if(MST_select(a,ds) == Cost) secondary_cnt++;
    }

    cout << Cost <<'\n' << essential_cnt <<'\n' << secondary_cnt <<'\n';
    return 0;
}