//Algoritmul lui Kruscal

#define MAX_N 200001
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct structAdiacenta {
    int from;
    int to;
    int cost;
};

typedef vector<structAdiacenta> adiacente_t;

int n, m;
adiacente_t adiacente[MAX_N];
adiacente_t toateMuchiile;

int paduri[MAX_N];

int rezultatTotal;
adiacente_t rezultat;


void kruscal();

bool sortare(const structAdiacenta &a, const structAdiacenta &b) {
    return a.cost < b.cost;
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; i++) {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        structAdiacenta structX;
        structX.from = x;
        structX.to = y;
        structX.cost = c;
        adiacente[x].push_back(structX);

        structAdiacenta structY;
        structY.from = y;
        structY.to = x;
        structY.cost = c;
        adiacente[y].push_back(structY);

        toateMuchiile.push_back(structX);
    }

    kruscal();

    printf("%d\n", rezultatTotal);
    printf("%d\n", rezultat.size());
    for (adiacente_t::const_iterator i = rezultat.begin(); i != rezultat.end(); ++i) {
        printf("%d %d\n", i->from, i->to);
    }

    return 0;
}

// -------- ALGORITMUL LUI KRUSCAL ---------

int grupa(int nod) {
    if (paduri[nod] == nod)
        return nod;
    paduri[nod] = grupa(paduri[nod]);
    return paduri[nod];
}

void reuniune(int nodA, int nodB) {
    paduri[grupa(nodA)] = grupa(nodB);
}

void kruscal() {
    for (int i = 1; i <= n; i++)
        paduri[i] = i;
    sort(toateMuchiile.begin(), toateMuchiile.end(), sortare);
    for (adiacente_t::const_iterator i = toateMuchiile.begin(); i != toateMuchiile.end(); ++i) {
        if (grupa(i->from) != grupa(i->to)) {
            rezultatTotal += i->cost;
            reuniune(i->from, i->to);
            rezultat.push_back(*i);
        }
    }
}