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

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

#define MMAX 400001
#define NMAX 200001
int n, m;
struct Muchie{
    int x, y, c;
} muc[MMAX];
//int C[NMAX];
int tata[NMAX], h[NMAX];
Muchie sol[NMAX];

bool condition(Muchie a, Muchie b) {
    if (a.c < b.c) {
        return 1;
    }
    return 0;
}

int Find(int x) {
    int r, y;
    ///mai intai aflu radacina arborelui din care face parte x
    r = x;
    while (tata[r] != r) {
        r = tata[r];
    }
    ///parcurg din nou drumul de la x la r si fac toate nodurile fii ai lui r

    while (tata[x] != r) {
        y = tata[x];
        tata[x] = r;
        x = y;
    }

    return r;
}

void Union(int x, int y) {

    int rx = Find(x);
    int ry = Find(y);

    if (rx != ry) {
        if (h[rx] < h[ry]) {
            tata[rx] = ry;
        } else if (h[ry] < h[rx]) {
            tata[ry] = rx;
        } else {
            tata[ry] = rx, h[ry]++;
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i<=m; i++) {
        fin >> muc[i].x >> muc[i].y >> muc[i].c;
    }
    for (int i = 1; i<=n; i++) {
        h[i] = 1, tata[i] = i;
    }
    sort(muc+1, muc+m+1, condition);

    int taken = 0, i = 1;
    int sum = 0;

    while (taken < n-1 && i<=m) {
        if (Find(muc[i].x) != Find(muc[i].y)) {
            Union(muc[i].x, muc[i].y);
            sol[++taken] = muc[i];
            sum += muc[i].c;

        }
        i++;
    }

    fout << sum << "\n" << taken << "\n";
    for (int i = 1; i<=taken; i++) {
        fout << sol[i].x << " " << sol[i].y << "\n";
    }

    return 0;
}