#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 501100
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m;

struct Muchie {
    int x, y, cost;
}e[NMAX], answer[NMAX];

pair<int, pair<int, int> > paaa;

bool cmp(Muchie e1, Muchie e2) {
    if (e1.cost > e2.cost) {
        return false;
    }
    return true;
}

int tata[NMAX], fiu[NMAX], sizeOf[NMAX], nextElem[NMAX];

void mergeElem(int m1, int m2) {

    sizeOf[tata[m2]] += sizeOf[tata[m1]];
    int fiuMare = fiu[tata[m2]];
    int tataMic = tata[m1];
    nextElem[fiuMare] = tataMic;
    fiu[tata[m2]] = fiu[tata[m1]];
    int currentElem = tata[m1];
    int lastNode = fiu[tata[m1]];
    while (currentElem != lastNode) {
        tata[currentElem] = tata[m2];
        currentElem = nextElem[currentElem];
    }
    tata[currentElem] = tata[m2];

}


int main() {

    f >> n >> m;
    for (int i = 0; i < m; ++i) {
        f >> e[i].x >> e[i].y >> e[i].cost;
        e[i].x --;
        e[i].y --;
    }

    sort(e, e + m, cmp);
    for (int i = 0; i < n; ++i) {
        tata[i] = i;
        fiu[i] = i;
        sizeOf[i] = 1;
        nextElem[i] = i;
    }
    long long int costFinal = 0;
    int nrElem = 0;
    for (int i = 0; nrElem < n - 1; ++i) {
        if (tata[e[i].x] != tata[e[i].y]) {

            answer[nrElem].x = e[i].x;
            answer[nrElem].y = e[i].y;

            nrElem ++;
            costFinal = costFinal + e[i].cost;

            if (sizeOf[tata[e[i].x]] > sizeOf[tata[e[i].y]] ) {
                mergeElem(e[i].y, e[i].x);
            } else {
                mergeElem(e[i].x, e[i].y);
            }
        }
    }

    g << costFinal << "\n" << nrElem << "\n";

    for (int i = 0; i < nrElem; ++i) {
        g << answer[i].x + 1 << " " << answer[i].y + 1 << "\n";
    }

    return 0;
}