#include <stdio.h>

typedef struct _muchie{
    int e1, e2, cost;
} muchie;

int m,n;
muchie mc[400000+1];

void read_data(){
    FILE *fIn;
    int i;

    fIn = fopen("apm.in", "r");

    fscanf(fIn, "%d %d", &n , &m);

    for(i = 1; i <= m; i++)
        fscanf(fIn, "%d %d %d", &(mc[i].e1), &(mc[i].e2), &(mc[i].cost));

    fclose(fIn);
}

void q_sort(int st, int dr){
    if(st >= dr)
        return;

    int b,i,k;
    muchie tmp;
    
    k = st;
    b = mc[st].cost;
    for(i = st; i <= dr; i++){
        if(mc[i].cost < b){
            k++;
            tmp = mc[i];
            mc[i] = mc[k];
            mc[k] = tmp;   
        }
    }

    tmp = mc[k];
    mc[k] = mc[st];
    mc[st] = tmp;

    q_sort(st, k-1);
    q_sort(k+1, dr);
}

int main(){
    read_data();

    //Sortez elementele
    q_sort(1, m);
 
    long cost = 0;
    int i,j, k=0,nn;
    int b[400000+1] = {0},sol[400000+1] = {0};

    //Tabloul ajutator
    for(i = 1; i <= n; i++)
        b[i] = i;

    for(i = 1; i <= m; i++){
        if(b[mc[i].e1] != b[mc[i].e2]){
            sol[++k] = i;
            cost += mc[i].cost;
            
            nn = b[mc[i].e1];
            for(j = 1; j <= n; j++){
                if(b[j] == nn)
                    b[j] = b[mc[i].e2];
            }
        }
    }
    
    FILE *fOut = fopen("apm.out", "w");
    fprintf(fOut, "%ld\n%d\n", cost, k);
    for(i = 1; i <= k; i++)
        fprintf(fOut, "%d %d\n", mc[sol[i]].e1, mc[sol[i]].e2); 
    fclose(fOut);      
          
    return 0;
}