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<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000;
const int mMax=100010;
const int inf=1000010;

int n,m,map[nMax][nMax],mark[mMax],mpp[nMax][nMax];
//

int dis[nMax],fff[nMax],ans,mintree[nMax][2],nk;
int prim(bool isis){   //  自己的prim模板。
    int i, j, now,aaa,bbb;
    int  min_node, min_edge;
    for(i = 1; i <=n; i ++)
        dis[i] = inf-10;
    now = 1;
    ans = 0;
    nk=1;
    for(i = 0; i < n-1; i ++){
        dis[now] = -1;    //   将dis[]的&#20540;&#36171;-1，表示已&#32463;加入生成&#26641;中。
        min_edge = inf;
        for(j = 1; j <= n; j ++)    //   更新&#27599;个&#39030;点所&#23545;&#24212;的dis[]&#20540;。
            if(now != j && dis[j] >= 0 ){
                if(map[now][j]<dis[j]){
                    dis[j]=map[now][j];
                    fff[j]=now;
                }
                if(dis[j] < min_edge){
                    min_edge = dis[j];
                    min_node = j;
                }
            }
        now = min_node;
       if(isis==1){
            aaa=now;
            bbb=fff[now];
            mintree[nk][0]=aaa;
            mintree[nk++][1]=bbb;
       }
        ans += min_edge;
    }
    return ans;
}

int val[mMax];
int main(){
    int i,j,a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(i=1;i<=n;i++)for(j=1;j<=n;j++)map[i][j]=inf;
        memset(mark,0,sizeof(mark));
        for(i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            map[a][b]=map[b][a]=c;
            mpp[a][b]=mpp[b][a]=i;
            val[i]=c;
        }

        int sum = prim(1);
        a=map[mintree[1][0]][mintree[1][1]];
        map[mintree[1][0]][mintree[1][1]]=map[mintree[1][1]][mintree[1][0]]=inf;
        if(sum!=prim(0)){
            mark[mpp[mintree[1][0]][mintree[1][1]]]=1;
        }
        for(i=2;i<=n-1;i++){
            map[mintree[i-1][0]][mintree[i-1][1]]=map[mintree[i-1][1]][mintree[i-1][0]]=a;
            if(mark[mpp[mintree[i][0]][mintree[i][1]]])continue;
            a=map[mintree[i][0]][mintree[i][1]];
            map[mintree[i][0]][mintree[i][1]]=map[mintree[i][1]][mintree[i][0]]=inf;
            b=prim(0);
//            cout<<b<<endl;
            if(sum!=b){
                mark[mpp[mintree[i][0]][mintree[i][1]]]=1;
            }
        }
        ans=0,sum=0;
        for(i=1;i<=m;i++){
            if(mark[i]){
                ans++;
                sum+=val[i];
            }
        }
        printf("%d %d\n",ans,sum);
    }
    return 0;
}