#include <stdio.h>

int cost[400001];
int m1[400001], m2[400001];
int sol1[400001], sol2[400001];
int nod[200001];

int sef[200001];

void quicksort(int begin, int end) {
    int aux, b, e,
    pivot;
    
    pivot = cost[(begin+end)/2];
    b = begin;
    e = end;
    
    while (cost[b] < pivot) {
        b++;
    }
    
    while (cost[e] > pivot) {
        e--;
    }
    
    while(b < e) {
        aux = cost[b];
        cost[b] = cost[e];
        cost[e] = aux;
        aux = m1[b];
        m1[b] = m1[e];
        m1[e] = aux;
        aux = m2[b];
        m2[b] = m2[e];
        m2[e] = aux;
        do {
            b++;
        }while (cost[b] < pivot);
        
        do {
            e--;
        } while (cost[e] > pivot);
    }
    
    
    if (begin < e) {
        quicksort(begin, e);
    }
    
    if (e+1 < end) {
        quicksort(e + 1, end);
    }
}

int sefsuprem(int x) {
    if(sef[x] == x) {
        return x;
    }
    return sef[x] = sefsuprem(sef[x]);
}

int main() {
    FILE *fin, *fout;
    fin = fopen("apm.in", "r");
    fout = fopen("apm.out", "w");
    
    int n, m, i, nrm, sumcost, sef1, sef2;
    
    fscanf(fin, "%d%d", &n, &m);
    
    for (i=0; i<m; i++) {
        fscanf(fin, "%d%d%d", &m1[i], &m2[i], &cost[i]);
    }
    
    quicksort( 0, m - 1 );

    
//    for (i=0; i<m; i++) {
//        fprintf(fout, "%d %d %d\n", m1[i], m2[i], cost[i]);
//    }
    
    for (i=0; i<n; i++) {
        sef[i] = i;
    }
    
    nrm = 0;
    sumcost = 0;
    for (i=0; i<m && nrm<n-1; i++) {
        sef1 = sefsuprem(m1[i]);
        sef2 = sefsuprem(m2[i]);
        if (sef1!=sef2) {
            sol1[nrm] = m1[i];
            sol2[nrm] = m2[i];
            sef[sef1] = sef2;
            nrm++;
            sumcost += cost[i];
        }
        
    }
    
    fprintf(fout, "%d\n%d\n", sumcost, n-1);
    
    for (i=0; i<n-1; i++) {
        fprintf(fout, "%d %d\n", sol1[i], sol2[i]);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}