#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 toateMuchiile;

int paduri[MAX_N];

int rezultatTotal;
adiacente_t rezultat;


void kruskal();

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;

        toateMuchiile.push_back(structX);
    }

    kruskal();

    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->to, i->from);
    }

    return 0;
}

// -------- ALGORITMUL LUI KRUSKAL ---------

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

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

void kruskal() {
    for (int i = 1; i <= n; i++)
        paduri[i] = 0;
    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);
        }
    }
}