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