#include <stdio.h>
#include <stdlib.h>

typedef struct _edge {
    int source, dest, cost;
}edge;

int Find(int x, int *c) {
    int y = x, t;
    while(y != c[y])
        y = c[y];

    while(x != y) {
        t = c[x];
        c[x] = y;
        x = t;
    }

    return x;
}

void Unite(int x, int y, int *c) {
    x = Find(x, c);
    y = Find(y, c);
    c[y] = x;
}

int cmp_edges(const void *pa, const void *pb) {
    edge a = *(edge *)pa;
    edge b = *(edge *)pb;

    return a.cost-b.cost;
}

int APM_Kruskal(int n, int *c, int m, edge *e, edge *out) {
    int cost = 0, sz = 0;

    for(int i = 0; i < m; i++) {
        int x = e[i].source, y = e[i].dest, z = e[i].cost;
        if(Find(x, c) != Find(y, c)) {
            Unite(x, y, c);
            cost+=z;
            out[sz++] = e[i];
        }
    }

    return cost;
}

int main() {

    FILE *input = fopen("apm.in", "r");
    FILE *output = fopen("apm.out", "w");
    int n, m, *c, type, a, b;
    edge *e, *out;

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

    c = (int *) calloc(n + 1, sizeof(int));
    e = (edge *) calloc(m, sizeof(int));
    out = (edge *) calloc(n - 1, sizeof(int));

    for(int i = 1; i <= n; i++)
        c[i] = i;

    for(int i = 0; i < m; i++)
        fscanf(input, "%d %d %d", &e[i].source, &e[i].dest, &e[i].cost);

    qsort(e, m, sizeof(edge), cmp_edges);

    int apm_cost = APM_Kruskal(n, c, m, e, out);
    fprintf(output, "%d\n", apm_cost);

    fprintf(output, "%d\n", n - 1);

    for(int i = 0; i < n - 1; i++) {
        fprintf(output, "%d %d\n", out[i].source, out[i].dest);
    }

    free(c);
    free(e);
    fclose(input);
    fclose(output);

    return 0;
}