#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 Muchii{ long int x, y, c; } v[MAXM];

long int N, M, HSOL=0, Cmin=0;
long int T[MAXN], H[MAXN], SOL[MAXN];

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( Muchii A, Muchii B ){
    if( A.c < B.c ) return 1; return 0;
}

long int Grupa( long int nod ){
long int r, rr, rrr;

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

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

    return r;
}

long int Uneste( long int G1, long int G2 ){

    if( H[G1] > H[G2] ){ T[G2]=G1; }
    else if( H[G1] < H[G2] ){ T[G1]=G2; }
    else { T[G1]=G2; H[G2]++; }

}

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;
            Uneste( Grupa( v[i].x ), Grupa( v[i].y ) );
            SOL[++HSOL]=i;
            if( HSOL == N-1 ) break;
        }

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

return 0;
}