#include <stdio.h>

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

int sef[200001];

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, max, p, u, max1, max2, nrm, ok1, ok2, j, nrnod, 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]);
    }
    
    for (u=m-1; u>0; u--) {
        max = cost[0];
        max1 = m1[0];
        max2 = m2[0];
        p = 0;
        for (i=1; i<=u; i++) {
            if (cost[i]>max) {
                max = cost[i];
                p = i;
                max1 = m1[i];
                max2 = m2[i];
            }
        }
        cost[p] = cost[u];
        cost[u] = max;
        
        m1[p] = m1[u];
        m1[u] = max1;
        
        m2[p] = m2[u];
        m2[u] = max2;
    }
    
//    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;
}