#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct arch {
    int start, end, cost;
};

const int MAX_PEAKS = 200005;
const int MAX_ARCHES = 400005;

int noPeaks, noArches, representants[MAX_PEAKS];
arch arches[MAX_ARCHES];

int costCriteria(arch cost1, arch cost2) {
    return cost1.cost < cost2.cost;
}

int main() {
    fin >> noPeaks >> noArches;
    for (int i = 1 ; i <= noArches ; ++i) {
        fin >> arches[i].start >> arches[i].end >> arches[i].cost;
    }
    sort(arches + 1, arches + 1 + noArches, costCriteria); // sorts by cost
    int minSum = 0, noUnitedTreeArches = 0;
    arch unitedTree[MAX_ARCHES];
    for (int i = 1; i <= noArches; ++i) { // iterates through all the "sorted by cost" arches
        if (representants[arches[i].start] != representants[arches[i].end] || representants[arches[i].start] == 0 || representants[arches[i].end] == 0) { // if it unites 2 different trees
            if (representants[arches[i].start] == 0) {
                representants[arches[i].start] = i;
            }
            if (representants[arches[i].end] == 0) {
                representants[arches[i].end] = i;
            }
            unitedTree[++noUnitedTreeArches].start = arches[i].start;
            unitedTree[noUnitedTreeArches].end = arches[i].end;
            minSum += arches[i].cost;
            int firstRepresentant = representants[arches[i].start], secondRepresentant = representants[arches[i].end]; // we unite the 2 separate trees
            for (int j = 1; j <= noPeaks; ++j) { // we mark the elements from the other tree with the first representant
                if (representants[j] == secondRepresentant) {
                    representants[j] = firstRepresentant;
                }
            }
        }
    }
    fout << minSum << "\n" << noUnitedTreeArches << "\n";
    for (int i = 1; i <= noUnitedTreeArches; ++i) {
        fout << unitedTree[i].start << " " << unitedTree[i].end << "\n";
    }
    return 0;
}