#include<cstdio>
#include<algorithm>
#define MAXN 200005
#define MAXM 4000005
FILE *f=fopen("apm.in","r"), *g=fopen("apm.out","w");

using namespace std;

struct Muchii{ int x, y, c; } m[MAXM];

int N, M, SOL[MAXN], LSOL = 0, H[MAXN], T[MAXN], Ctotal = 0;

bool cmp( Muchii A, Muchii B ){

    if( A.c < B.c )
        return 1;
        return 0;
}

void Citire(){
int i;

    fscanf(f,"%d %d\n",&N,&M);

    for(i=1;i<=M;i++)
        fscanf(f,"%d %d %d\n",&m[i].x,&m[i].y,&m[i].c);

    sort(m+1,m+M+1,cmp);

}

int Grupa( int NOD ){
int R, RR, oldRR;

    R = NOD;
    while( T[R] != 0 )
        R = T[R];

    RR = NOD;
    while( T[RR] != 0 ){

        oldRR = RR;

        RR = T[RR];

        T[oldRR] = R;

    }

    return R;
}

void Uneste( int UNU, int DOI ){

    if( H[DOI] < H[UNU] ){

        T[DOI] = UNU;

    }
    else if( H[DOI] > H[UNU] ){

        T[UNU] = DOI;

    }
    else{

        T[UNU] = DOI;
        H[DOI] = H[UNU]+1;

    }

}

void Rezolvare(){
int i, X, Y, C, GrupaX, GrupaY;

    for(i=1;i<=M;i++){

        X = m[i].x;
        Y = m[i].y;
        C = m[i].c;

        GrupaX = Grupa(X);
        GrupaY = Grupa(Y);

        if( GrupaX != GrupaY ){

            Uneste(GrupaX,GrupaY);
            SOL[++LSOL] = i;
            Ctotal += C;

        }

        if( LSOL == N-1 )
            break;

    }

}

void Afisare(){
int i;

    fprintf(g,"%d\n",Ctotal);

    fprintf(g,"%d\n",N-1);
    for(i=1;i<=N-1;i++)
        fprintf(g,"%d %d\n", m[ SOL[i] ].x, m[ SOL[i] ].y );

}

int main(){

    Citire();
    Rezolvare();
    Afisare();

return 0;
}