#include <bits/stdc++.h>
#define inputFile "apm.in"
#define outputFile "apm.out"

using namespace std;

ifstream in(inputFile);
ofstream out(outputFile);

struct edge{
    unsigned x, y;
    int c;
};

struct pereche{
    unsigned u, v;
};

bool cond(edge a, edge b)
{
    return a.c <= b.c;
}

int main(void)
{
    unsigned N, M;
    in >> N >> M;
    edge e[M];
    for(unsigned i = 0; i < M; ++i)
        in >> e[i].x >> e[i].y >> e[i].c;
    sort(e, e + M, &cond);
    unsigned gr[N + 1];
    memset(gr, 0, sizeof(gr));
    unsigned cont = 0, sel = 0;
    int costMinim = 0;
    pereche rez[N - 1];
    for(unsigned i = 0; i < M && sel + 1 < N; ++i)
    {
        if(gr[e[i].x] && gr[e[i].y] && gr[e[i].x] == gr[e[i].y])
            continue;
        if(!gr[e[i].x] && !gr[e[i].y])
            gr[e[i].x] = gr[e[i].y] = ++cont;
        else if(!gr[e[i].x])
            gr[e[i].x] = gr[e[i].y];
        else if(!gr[e[i].y])
            gr[e[i].y] = gr[e[i].x];
        else{
            unsigned elim = gr[e[i].y];
            for(unsigned j = 1; j <= N; ++j)
            if(gr[j] == elim)
                gr[j] = gr[e[i].x];
        }
        costMinim += e[i].c;
        rez[sel] = {e[i].x, e[i].y};
        ++sel;
    }
    out << costMinim << endl << N - 1;
    for(unsigned i = 0; i + 1 < N; ++i)
        out << endl << rez[i].u << ' ' << rez[i].v;
    return 0;
}