#include <stdio.h>
#include <stdlib.h>
#define w(n,t) (t*)malloc((n)*sizeof(t))
#define fr(i,a,b) for(i=a;i<b;++i)
int*o,*O,*c,*I,*p,*P;
int g(int i){
    int j=i;
    while(j!=p[j])j=p[j];
    return p[i]=j;
    }
void G(int i,int j){
    if(P[i]<P[j])i^=j^=i^=j;
    p[j]=i;
    P[i]+=P[i]==P[j];
    }
int cmp(const void*a,const void*b){return c[*(int*)a]-c[*(int*)b];}
int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,i;
    scanf("%i%i",&n,&m);
    o=w(m,int);O=w(m,int);c=w(m,int);I=w(m,int);
    fr(i,0,m)scanf("%i%i%i",o+i,O+i,c+i),I[i]=i,--O[i]-o[i]--;
    qsort(I,m,sizeof(*I),cmp);
    p=w(n,int);P=w(n,int);
    fr(i,0,n)p[i]=i,P[i]=1;
    int s=0,j;
    int*x=w(n-1,int),*X=w(n-1,int),y=0;
    fr(i,0,m){
        int a=o[I[i]],b=O[I[i]];
        int A=g(a),B=g(b);
        if(A==B)continue;
        x[y]=a,X[y++]=b;
        s+=c[I[i]];
        G(A,B);
        }
    printf("%i\n",s);
    printf("%i\n",y);
    fr(i,0,y)printf("%i %i\n",x[i]+1,X[i]+1);
    return 0;
    }