#include <stdio.h>
#include <algorithm>

#define MAX_N 200000
#define MAX_M 400000

using namespace std;

FILE *fin = fopen("apm.in", "r");
FILE *fout = fopen("apm.out", "w");

int N, M;
int boss[MAX_N + 1];

struct anakin{
    int node1, node2;
    int cost;
};

struct anakin2{
    int node1, node2;
};

anakin relat[MAX_M + 1];
anakin2 sol[MAX_N + 1];

int tfind(int a) {
    if (a == boss[a])
        return a;
    boss[a] = tfind(boss[a]);
    return tfind(boss[a]);
}

void tunion(int a, int b) {
    int fa, fb;
    fa = tfind(boss[a]);
    fb = tfind(boss[b]);
    if (fa != fb) {
        boss[fa] = fb;
    }
}

bool cmp(anakin a, anakin b) {
    if (a.cost >= b.cost)
        return false;
    return true;
}

int main(){
    int i, j;
    int x, y, c;

    fscanf(fin, "%d %d", &N, &M);
    for (i = 1; i <= M; i++) {
        fscanf(fin, "%d %d %d", &x, &y, &c);
        relat[i].node1 = x;
        relat[i].node2 = y;
        relat[i].cost = c;
    }

    sort(relat + 1, relat + M + 1, cmp);
    for (i = 1; i <= N; i++)
        boss[i] = i;

    int k = 0;
    int COST = 0;
    for (i = 1; i <= M; i++) {
        x = relat[i].node1;
        y = relat[i].node2;
        if (tfind(x) != tfind(y)) {
            tunion(x, y);
            sol[++k].node1 = x;
            sol[k].node2 = y;
            COST += relat[i].cost;
        }
    }

    fprintf(fout, "%d\n", COST);
    fprintf(fout, "%d\n", N - 1);
    for (i = 1; i <= k; i++)
        fprintf(fout, "%d %d\n", sol[i].node1, sol[i].node2);

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