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

using namespace std;

long int N, M, Tata[MAXN], Inaltime[MAXN], Cmin=0, Selectat[MAXM];

struct graf{
    long int x, y, c;
} v[MAXM];

void Citire(){
long int i;

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

}

bool cmp( graf A, graf B ){
    if( A.c < B.c ) return 1;
    return 0;
}

long int Grupa( long int X ){
long int R, r, rvechi;

    R=X;
    while( Tata[R] != 0 ) R = Tata[R];
    r=X;
    while( Tata[r] != 0 ){ rvechi = r; r = Tata[r]; Tata[rvechi] = R; }

    return R;
}

void Unire( long int X, long int Y ){

    X = Grupa(X); Y = Grupa (Y);
    if( Inaltime[X] > Inaltime[Y] ) Tata[Y] = X;
    else if( Inaltime[X] < Inaltime[Y] ) Tata[X] = Y;
    else { Tata[X] = Y; Inaltime[Y]++; } // egalitate

}

int main(){

    Citire();
    sort(v+1,v+M+1,cmp);
    for(long int i=1;i<=M;i++){

        if( Grupa( v[i].x ) != Grupa( v[i].y ) ){
            Cmin += v[i].c;
            Unire( v[i].x, v[i].y );
            Selectat[ ++Selectat[0] ] = i;
            if( Selectat[0] == N-1 ) break; // Daca avem deja N-1 muchii ne oprim
        }

    }
    fprintf(g,"%ld\n%ld\n",Cmin,N-1);
    for(long int i=1;i<=N-1;i++)
        fprintf(g,"%ld %ld\n", v[ Selectat[i] ].x, v[ Selectat[i] ].y );

return 0;
}