#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;
heapVals vals[200100];
int pos[200100], iterate = 0;
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 (pos[income.nod] == 0) {
        crt = ++iterate;
        pos[income.nod] = crt;
        vals[crt] = aux;
    } else {
        crt = pos[income.nod];
        if (vals[crt].cost > aux.cost)
            vals[crt] = aux;
    }

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

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

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

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

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

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

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

            crt = nxt;
            nxt = crt * 2;
        } else {
            nxt = 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;
}