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

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

int N, M, sum, nr, r[MAXN];
int T[MAXN], H[MAXN];

bool cmp( Muchie A, Muchie 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",&v[i].x,&v[i].y,&v[i].c);

    sort(v+1,v+M+1,cmp);
}

void Uneste( int a, int b ){

    if( H[a] == H[b] ){
        T[a] = b;
        H[b]++;
    }

    else if( H[a] < H[b] )  // Lipim a la b
        T[a] = b;

    else                    // Lipim b la a
        T[b] = a;
}

int Grupa( int nod ){
int Tnod, newTnod, oldTnod;

    Tnod = nod;
    while( T[Tnod] != 0 )
        Tnod = T[Tnod];

    newTnod = Tnod;
    Tnod = nod;
    while( T[Tnod] != 0 ){
        oldTnod = Tnod;
        Tnod = T[Tnod];
        T[oldTnod] = newTnod;
    }
    H[newTnod] = 1;
    return newTnod;
}

void Rezolvare(){
int i, G1, G2;

    nr  = 0;
    for(i=1; i<=M, nr<=N-2; i++){
        G1 = Grupa( v[i].x );
        G2 = Grupa( v[i].y );
        if( G1 != G2 )
        {
            Uneste( G1, G2 );
            r[++nr] = i;
        }
    }

    for(i=1;i<=nr;i++)
        sum += v[ r[i] ].c;

    fprintf(g,"%d\n%d\n",sum,nr);

    for(i=1;i<=nr;i++)
        fprintf(g,"%d %d\n",v[ r[i] ].x,v[ r[i] ].y);

}

int main(){

    Citire();
    Rezolvare();

return 0;
}