#include <fstream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;

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

const int NMAX = 200010;
const int MMAX = 400010;

struct muchie {int fr, to, cost;} m[MMAX];

int N, M;
int ANSCost = 0, ANSMuchii = 0;
int ANS[MMAX];

bool criteriu (muchie a, muchie b) {
    return a.cost < b.cost;
}

int dad[NMAX];
void initUF () {
    for (int i = 1; i <= N; i++) {
        dad[i] = i;
    }
}

int fFind (int x) {
    if (dad[dad[x]] != dad[x]) {
        dad[x] = fFind (dad[x]);
    }

    return dad[x];
}

void fUnion (int dx, int dy) {
    if (rand() % 2) {
        dad[dy] = dx;
    }
    else {
        dad[dx] = dy;
    }
}

int main () {
    srand (time (NULL));

    fin >> N >> M;
    for (int i = 1; i <= M; i++) {
        fin >> m[i].fr >> m[i].to >> m[i].cost;
    }

    sort (m + 1, m + M + 1, criteriu);

    initUF();

    for (int i = 1; i <= M; i++) {
        int dfr = fFind(m[i].fr);
        int dto = fFind(m[i].to);

        if (dfr != dto) {
            fUnion (dfr, dto);

            ANSCost += m[i].cost;
            ANSMuchii++;
            ANS[ANSMuchii] = i;
        }
    }

    fout << ANSCost << "\n" << ANSMuchii << '\n';
    for (int i = 1; i <= ANSMuchii; i++) {
        fout << m[ANS[i]].fr << " " << m[ANS[i]].to << '\n';
    }

    return 0;
}