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

int n, m, i, x, y, c, APMcost, nodesInArb;
bool inAPM[200100];
list<pair<int, int> > graf[200100], solution;
struct heapStruct{ int nod, cost, connect; } minHeap[200100], best; int heapPointer = 1;

void addToHeap(pair<int, int> val, int cnct) {
    int crt = heapPointer;
    heapStruct aux;
    aux.nod = val.first; aux.cost = val.second; aux.connect = cnct;

    minHeap[heapPointer] = aux;
    heapPointer++;

    while (crt / 2 != 0 && minHeap[crt].cost < minHeap[crt/2].cost) {
        aux = minHeap[crt / 2];
        minHeap[crt / 2] = minHeap[crt];
        minHeap[crt] = aux;
        crt /= 2;
    }
}

heapStruct minFromHeap() {
    int crt = 1, nxt = 2;
    heapStruct ans = minHeap[1], aux;

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

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

        crt = nxt;
        nxt *= 2;
    }

    return ans;
}

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

    inAPM[1] = true; nodesInArb = 1;
    for (list<pair<int, int> >::iterator it = graf[1].begin() ; it != graf[1].end() ; it++)
        addToHeap(*it, 1);
    while(heapPointer > 1 && nodesInArb < n) {
        do {
            best = minFromHeap();
        } while (inAPM[best.nod] == true);
        inAPM[best.nod] = true;
        APMcost += best.cost;
        solution.push_back(make_pair(best.connect, best.nod));
        nodesInArb++;

        for (list<pair<int, int> >::iterator it = graf[best.nod].begin() ; it != graf[best.nod].end() ; it++) {
            if ( !inAPM[it->first] )
                addToHeap(*it, best.nod);
        }
    }

    fout<<APMcost<<'\n';
    fout<<solution.size()<<'\n';
    for (list<pair<int, int> >::iterator it = solution.begin() ; it != solution.end() ; it++) {
        fout<<it->first<<' '<<it->second<<'\n';
    }

    return 0;
}