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

int n, m, i, x, y, c, APMcost;
bool inAPM[200100];
struct edge{int nod, cost; };
struct heapVals{int nod, cost, from; } best;
struct {heapVals vals[200100]; int pos[200100], iterate = 0; } minHeap;
list<edge> graf[200100], solution;

edge mPair(int x, int y) {
    edge ans;
    ans.nod = x; ans.cost = y;
    return ans;
}

void addHeap(edge income, int from) {
    int crt, nxt;
    heapVals aux;

    aux.nod = income.nod; aux.cost = income.cost; aux.from = from;
    if (minHeap.pos[income.nod] == 0) {
        crt = ++minHeap.iterate;
        minHeap.pos[income.nod] = crt;
        minHeap.vals[crt] = aux;
    } else {
        crt = minHeap.pos[income.nod];
        if (minHeap.vals[crt].cost > aux.cost)
            minHeap.vals[crt] = aux;
    }

    nxt = crt / 2;
    while (nxt >= 1 && minHeap.vals[nxt].cost > minHeap.vals[crt].cost) {
        minHeap.pos[ minHeap.vals[nxt].nod ] = crt;
        minHeap.pos[ minHeap.vals[crt].nod ] = nxt;

        aux = minHeap.vals[nxt];
        minHeap.vals[nxt] = minHeap.vals[crt];
        minHeap.vals[crt] = aux;

        crt = nxt;
        nxt = crt / 2;
    }
}

heapVals fromHeap() {
    int crt = 1, nxt = 2;
    heapVals aux, ans = minHeap.vals[1];

    minHeap.vals[1] = minHeap.vals[ minHeap.iterate-- ];
    while (nxt <= minHeap.iterate) {
        if (nxt < minHeap.iterate && minHeap.vals[nxt].cost > minHeap.vals[nxt + 1].cost)
            nxt++;

        if (minHeap.vals[crt].cost > minHeap.vals[nxt].cost) {
            minHeap.pos[ minHeap.vals[nxt].nod ] = crt;
            minHeap.pos[ minHeap.vals[crt].nod ] = nxt;

            aux = minHeap.vals[nxt];
            minHeap.vals[nxt] = minHeap.vals[crt];
            minHeap.vals[crt] = aux;

            crt = nxt;
            nxt = crt * 2;
        } else {
            nxt = minHeap.iterate + 1;
        }
    }

    return ans;
}

int main()
{
    fin>>n>>m;
    for (i = 1 ; i <= m ; i++) {
        fin>>x>>y>>c;
        graf[x].push_back(mPair(y, c));
        graf[y].push_back(mPair(x, c));
    }

    inAPM[1] = true;
    for (list<edge>::iterator it = graf[1].begin() ; it != graf[1].end() ; it++)
        addHeap(*it, 1);

    for (i = 1 ; i < n ; i++) {
        best = fromHeap();
        inAPM[best.nod] = true;
        APMcost += best.cost;
        solution.push_back(mPair(best.from, best.nod));

        for (list<edge>::iterator it = graf[best.nod].begin() ; it != graf[best.nod].end() ; it++)
            if (!inAPM[it->nod])
                addHeap(*it, best.nod);
    }

    fout<<APMcost<<'\n';
    fout<<n-1<<'\n';
    for (list<edge>::iterator it = solution.begin() ; it != solution.end() ; it++) {
        fout<<it->nod<<' '<<it->cost<<'\n';
    }

    return 0;
}