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

int n, m, i, x, y, c, APMcost;
bool inAPM[200100], edgeFound;
list<pair<int, int> > graf[200100], solution;
pair<int, int> minHeap[200100], best; int heapPointer = 1;

void addToHeap(pair<int, int> val) {
    int crt = heapPointer;
    pair<int, int> aux;

    minHeap[heapPointer] = val;
    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;
    }
}

pair<int, int> minFromHeap() {
    int crt = 1, nxt = 2;
    pair<int, int> 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;
    for (list<pair<int, int> >::iterator it = graf[1].begin() ; it != graf[1].end() ; it++)
        addToHeap(*it);
    while(heapPointer > 1) {
        do {
            best = minFromHeap();
        } while (inAPM[best.nod] == true);
        edgeFound = false;
        inAPM[best.nod] = true;

        for (list<pair<int, int> >::iterator it = graf[best.nod].begin() ; it != graf[best.nod].end() ; it++) {
            if (it->cost == best.cost && !edgeFound && inAPM[it->nod]) {
                edgeFound = true;
                solution.push_back(make_pair(it->nod, best.nod));
                APMcost += best.cost;
            }

            if ( !inAPM[it->nod] ) {
                addToHeap(*it);
            }
        }
    }

    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;
}