#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;

int N, M, CostT = 0, LSol, Sol[MAXN], T[MAXN], H[MAXN];

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

void Citire(){
int i;

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

}

bool cmp( Muchie A, Muchie B ){

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

}

int Grupa( int nod ){
int R, r, rr;

    R = nod;
    while( R != T[R] )
        R = T[R];

    r = nod;
    while( r != T[r] ){
        rr = r;
        r = T[r];
        T[rr] = R;
    }

    return R;
}

void Uneste( int A, int B ){

    if( H[A] < H[B] )
        T[A] = B;

    else if( H[B] < H[A] )
             T[B] = A;

    else{ T[A] = B; H[B]++; }

}

void Rezolvare(){
int i, nrmuchii=0, Gx, Gy;

    for(i=1;i<=N;i++)
        T[i] = i;

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

        Gx = Grupa( v[i].x );
        Gy = Grupa( v[i].y );

        if( Gx != Gy ){

            Uneste( Gx, Gy );

            Sol[++LSol] = i;
            CostT += v[i].c;

            nrmuchii++;
            if( nrmuchii == N-1 )
                break;

        }

    }
    fprintf(g,"%d\n%d\n",CostT,LSol);
    for(i=1;i<=LSol;i++)
        fprintf(g,"%d %d\n", v[ Sol[i] ].x, v[ Sol[i] ].y );

}

int main(){

    Citire();
    sort(v+1,v+M+1,cmp);
    Rezolvare();

return 0;
}