#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, i, edgy, tataX, tataY, apmCost, TT[200100], RNK[200100];
struct muchie{int x, y, c;} v[400100];
struct {int x, y;} solution[200100];

bool cmp(muchie a, muchie b) {
    return a.c < b.c;
}

int root (int val) {
    int R = val, aux;
    while (TT[R] != R) R = TT[R];
    while (TT[val] != val) {
        aux = val;
        val = TT[val];
        TT[aux] = R;
    }

    return R;
}

void couple (int rootX, int rootY) {
    if (RNK[rootX] > RNK[rootY])
        TT[rootY] = rootX;
    else
        TT[rootX] = rootY;

    if (RNK[rootX] == RNK[rootY])
        RNK[rootY]++;
}

int main()
{
    fin>>n>>m;
    for (i = 1 ; i <= n ; i++)
        TT[i] = i, RNK[i] = 1;
    for (i = 1 ; i <= m ; i++)
        fin>>v[i].x>>v[i].y>>v[i].c;
    sort(v + 1, v + m + 1, cmp);

    for (i = 1 ; i <= m ; i++) {
        tataX = root(v[i].x); tataY = root(v[i].y);
        if (tataX != tataY) {
            couple(tataX, tataY);
            apmCost += v[i].c;
            edgy++;
            solution[edgy].x = v[i].x, solution[edgy].y = v[i].y;
        }
    }

    fout<<apmCost<<'\n'<<n-1<<'\n';
    for (i = 1 ; i <= edgy ; i++)
        fout<<solution[i].y<<' '<<solution[i].x<<'\n';

    return 0;
}