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

#define N 200000
#define M 400000
#define NIL -1

struct aux_muchie {
    int x, y, c;
};

typedef struct aux_muchie muchie;

int n, m;
bool in_apm[M];
muchie vm[M];
int t[N+1], nr[N+1];

int radacina(int x) {
    if (t[x] == 0) {
        return x;
    }
    t[x] = radacina(t[x]);
    return t[x];
}

void reuniune(int x, int y) {
    int rx = radacina(x);
    int ry = radacina(y);
    if (nr[x] < nr[y]) {
        t[rx] = ry;
        nr[ry] += nr[x];
    } else {
        t[ry] = rx;
        nr[rx] += nr[y];
    }
}

bool acelasi_arbore(int x, int y) {
    return (radacina(x) == radacina(y));
}

int cmp(const void* p1, const void* p2) {
    muchie* pm1 = (muchie*)p1;
    muchie* pm2 = (muchie*)p2;
    return (pm1->c - pm2->c);
}

int main(void) {
    FILE *in = fopen("apm.in", "r");
    FILE *out = fopen("apm.out", "w");
    int n, m;
    fscanf(in, "%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        nr[i] = 1;
    }
    for (int i = 0; i < m; i++) {
        fscanf(in, "%d%d%d", &vm[i].x, &vm[i].y, &vm[i].c);
    }
    qsort(vm, m, sizeof(muchie), cmp);
    int cost = 0, i_muchie = 0;
    for (int i = 0; i < n - 1; i++) {
        while (acelasi_arbore(vm[i_muchie].x, vm[i_muchie].y)) {
            i_muchie++;
        }
        in_apm[i_muchie] = true;
        cost += vm[i_muchie].c;
        reuniune(vm[i_muchie].x, vm[i_muchie].y);
    }
    fprintf(out, "%d\n%d\n", cost, n - 1);
    for (int i = 0; i < m; i++) {
        if (in_apm[i]) {
            fprintf(out, "%d %d\n", vm[i].x, vm[i].y);
        }
    }
    fclose(in);
    fclose(out);
    return 0;
}