#include<cstdio>
#include<algorithm>
using namespace std;
struct nod{
    int x;
    int y;
    int c;
}x[400100];
int n,m,a,b,ra,rb,i,j,s,nr,sol[200100],d[200100],t[200100];
FILE *f,*g;
int cmp(nod a,nod b){
    return a.c<b.c;
}
int rad(int a){
    while(t[a]>0)
        a=t[a];
    return a;
}
int main(){
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(f,"%d%d%d",&x[i].x,&x[i].y,&x[i].c);
    }
    for(i=1;i<=n;i++){
        t[i]=-1;
    }
    sort(x+1,x+m+1,cmp);
    for(i=1;i<=m;i++){
        ra=rad(x[i].x);
        rb=rad(x[i].y);
        if(ra!=rb){
            s+=x[i].c;
            sol[++nr]=i;
            if(t[ra]>t[rb]){
                t[rb]=t[rb]+t[ra];
                t[ra]=rb;
            }
            else{
                t[ra]=t[rb]+t[ra];
                t[rb]=ra;
            }
        }
    }
    fprintf(g,"%d\n%d\n",s,nr);
    for(i=1;i<=nr;i++){
        fprintf(g,"%d %d\n",x[ sol[i] ].x,x[ sol[i] ].y);
    }


    fclose(f);
    fclose(g);
    return 0;
}