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

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

int n, m;

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

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

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

void mergeElem(int m1, int m2) {

    int fiuMare = fiu[tata[m2]];
    int tataMic = tata[m1];
    sizeOf[tata[m2]] += sizeOf[tata[m1]];
    nextElem[fiuMare] = tataMic;
    fiu[tata[m2]] = fiu[tata[m1]];
    int currentElem = tata[m1];
    while (currentElem != nextElem[currentElem]) {
        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 cost = 0;
    int nrElem = 0;
    for (int i = 0; nrElem < n - 1; ++i) {
        if (tata[e[i].x] == tata[e[i].y]) {
            continue;
        }

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

        nrElem ++;
        cost = cost + 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 << cost << "\n" << nrElem << "\n";

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

    return 0;
}