#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;
    bool viz[200003];
    for(int i=1;i<=N;++i)
        viz[i] = false;

    //initial vizitam doar nodul 1
    noduri_vizitate.push_back(1);
    tata[1] = 0;
    viz[1]=true;

    //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++)
    {
        //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];
            //acum iau vecinii nevizitati ai lui x
            for(unsigned int j=0;j<L[x].size();++j)
            {
                int y = L[x][j].nod;
                if(viz[y]==false && L[x][j].cost<val_min)
                {
                    val_min = L[x][j].cost;
                    t = x;
                    nod_min = y;
                }

            }
        }

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