#include<fstream>
#include<queue>
#include<list>
#include<climits>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

const int Nmax = 200005;

bool Vizitat[Nmax];
int CostMinim[Nmax], Tata[Nmax], NrNoduri, NrMuchii;

struct graf{

    int Nod, Cost;
};

list<graf>Graf[Nmax];
list<graf>::iterator It;

class cmp{

public:
    bool operator () (const pair<int, int> &a, const pair<int, int> &b) const{

        return a.second > b.second;
    }
};
priority_queue< pair<int, int>, vector< pair<int, int> >, cmp> pq;

void citire(){

    f >> NrNoduri >> NrMuchii;

    int nod1, nod2, cost;
    while(NrMuchii--){

        f >> nod1 >> nod2 >> cost;
        Graf[nod1].push_back({nod2, cost});
        Graf[nod2].push_back({nod1, cost});
    }
}

void Prim(){

    int Indice;
    for(Indice = 1; Indice <= NrNoduri; ++Indice)
            CostMinim[Indice] = INT_MAX;

    int NodSursa = 1;
    CostMinim[NodSursa] = 0;

    pq.push(make_pair(NodSursa, CostMinim[NodSursa]));

    while(!pq.empty()){

        int NodCurent = pq.top().first;
        pq.pop();

        Vizitat[NodCurent] = true;

        for(It = Graf[NodCurent].begin(); It != Graf[NodCurent].end(); ++It){

            int NodVecin = It->Nod;
            int CostVecin = It->Cost;

            if(!Vizitat[NodVecin] and CostVecin < CostMinim[NodVecin]){

                CostMinim[NodVecin] = CostVecin;
                pq.push(make_pair(NodVecin, CostVecin));
                Tata[NodVecin] = NodCurent;
            }
        }
    }
}

void print(){

    int Indice, Cost = 0;
    for(Indice = 1; Indice <= NrNoduri; ++Indice)
        Cost += CostMinim[Indice];
    g << Cost << '\n' << NrNoduri - 1 << '\n';

    for(Indice = 2; Indice <= NrNoduri; ++Indice)
        g << Indice << ' ' << Tata[Indice] << '\n';
}

int main(){

    citire();
    Prim();
    print();
    return 0;
}