#include<cstdio>
#include<algorithm>
struct nod{
    int x;
    int y;
    int c;
}v[400100];
using namespace std;
int n,m,i,j,na,nb,t[400100],s,nr,l[400100],c[400100];
FILE *f,*g;
int cmp(nod a,nod b){
    return a.c<b.c;
}
int rad(int r){
    while(t[r]!=0)
        r=t[r];
    return r;
}
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",&v[i].x,&v[i].y,&v[i].c);
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m;i++){
        na=rad(v[i].x);
        nb=rad(v[i].y);
        if(na!=nb){
            s+=v[i].c;
            l[++nr]=v[i].x;
            c[nr]=v[i].y;
            if(na>nb)
                t[nb]=na;
            else
                t[na]=nb;
        }
    }
    fprintf(g,"%d\n%d\n",s,nr);
    for(i=1;i<=nr;i++){
        fprintf(g,"%d %d\n",l[i],c[i]);
    }




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