#include <stdio.h>
#define fr(i,a,b) for(i=a;i<b;++i)

typedef struct
{
    int fp,ep,s;
}el;
int n,m,i,ss=0,j;
int*par;
int*P;

int cmp(const void*a,const void*b) {return (((el*)a)->s - ((el*)b)->s);}

int getp(int a)
{
    int k=a;
    while(k!=par[k]) k=par[k];
    return par[a]=k;
}

void mergee(int a, int b)
{
    if(P[a]<P[b]) a^=b^=a^=b;
    par[b]=a;
    P[a]+=P[a]==P[b];
}

int main()
{
    freopen("apm.in","r",stdin);
    scanf("%d%d",&n,&m);
    par=(int*)malloc((n)*sizeof(int));
    P=(int*)malloc((n)*sizeof(int));
    el *t=(el*)malloc(m*sizeof(el));
    fr(i,0,m) scanf("%d%d%d",&t[i].fp,&t[i].ep,&t[i].s),--t[i].fp,--t[i].ep;
    fr(i,0,n) par[i]=i,P[i]=1;
    qsort(t,m,sizeof(el),cmp);
    int*x=(int*)malloc((n)*sizeof(int));
    int*y=(int*)malloc((n)*sizeof(int));
    int w=0;
    fr(i,0,m)
    {
        int A=getp(t[i].fp);
        int B=getp(t[i].ep);
        if(A==B) continue;
        x[w]=t[i].fp,y[w]=t[i].ep;++w;
        ss+=t[i].s;
        mergee(A,B);
    }

    printf("%d\n%d\n",ss,w);
    fr(i,0,w) printf("%d %d\n",++x[i],++y[i]);
    return 0;
}