#include <bits/stdc++.h>
#define INFINIT 2000000000

using namespace std;

struct Muchie{
    int nod,cost;
};

int N,M,SOL=0;
int tata[200003], vall[200003];
vector<Muchie>L[200003];

void Citire()
{
    int i,x,y,c;
    Muchie w;
    ifstream fin("apm.in");
    fin>>N>>M;
    for(i=1;i<=M;++i)
    {
        fin>>x>>y>>c;
        w.nod = y;
        w.cost = c;
        L[x].push_back(w);
        w.nod = x;
        L[y].push_back(w);
    }
    fin.close();
}

void Prim()
{
    vector<int>noduri_vizitate;
    int valoare[200003];
    bool viz[200003];
    for(int i=1;i<=N;++i)
        viz[i] = false;
    for(int i=1;i<=N;++i)
        valoare[i] = INFINIT;

    //initial vizitam doar nodul 1
    noduri_vizitate.push_back(1);
    valoare[1] = 0;
    tata[1] = 0;
    viz[1]=true;
    //am gasit nodul cu valoarea minima
    for(unsigned int i=0;i<L[1].size();++i)
    {
        int y = L[1][i].nod;
        if(L[1][i].cost < valoare[y])
            valoare[y] = L[1][i].cost;
    }

    //noi vrem sa gasim arborele partial de cost minim
    //orice arbore cu N noduri are exact N-1 muchii, deci facem chestia de mai jos de N-1 ori

    for(int pas=1;pas<=N-1;pas++)
    {
        //cout<<"pas = "<<pas<<"\n";
        //acum incerc sa gasesc o Muchie
        //aleg aceasta muchie sa fie cea mai mica posibil

        //parcurg lista nodurilor vizitate pana acum
        int val_min = INFINIT;
        int nod_min;
        int t;
        for(unsigned int i=0;i<noduri_vizitate.size();++i)
        {
            int x=noduri_vizitate[i];
            //cout<<"nodul "<<x<<":\n";
            //cout<<"L[x].size()="<<L[x].size()<<"\n";
            //acum iau vecinii nevizitati ai lui x
            for(unsigned int j=0;j<L[x].size();++j)
            {
                int y = L[x][j].nod;
                //cout<<"\tnodul "<<y<<", valoare[y]="<<valoare[y]<<"\n";
                //cout<<"\tx="<<x<<"\n";
                if(viz[y]==false && valoare[y]<val_min)
                {
                    val_min = valoare[y];
                    t = x;
                    nod_min = y;
                }

            }
        }
        //cout<<"\n";
        //cout<<"\tnod_min="<<nod_min<<"\n";
        //cout<<"\tval_min="<<val_min<<"\n";

        //am gasit nodul cu valoarea minima
        for(unsigned int i=0;i<L[nod_min].size();++i)
        {
            int y = L[nod_min][i].nod;
            if(L[nod_min][i].cost < valoare[y])
                valoare[y] = L[nod_min][i].cost;
        }

        tata[nod_min] = t;
        vall[nod_min] = val_min;
        viz[nod_min] = true;
        noduri_vizitate.push_back(nod_min);
    }
}

void Afisare()
{
    int i;
    ofstream fout("apm.out");
    SOL=0;
    for(i=2;i<=N;++i)
        SOL+=vall[i];
    fout<<SOL<<"\n";
    fout<<N-1<<"\n";
    for(i=2;i<=N;++i)
        fout<<i<<" "<<tata[i]<<"\n";
    fout.close();
}

int main()
{
    Citire();
    Prim();
    Afisare();

    return 0;
}