#include <fstream>
#define Nmax 400000
using namespace std;

struct muchie
{
    int c1,c2;//capetele
    int cost;
};

void citire(int &N,int &M,muchie X[])
{ifstream in("apm.in");
    in>>N>>M;

//construim muchiile
    for(int i=0;i<M;i++)
        in>>X[i].c1>>X[i].c2>>X[i].cost;

in.close();
}

void Bubble_Sort(int M,muchie X[])
{
    int nS=0;//numarul de elemente sortate
    bool sortat;
    muchie aux;

    do
    {
        sortat=true;//presupunem ca este sortat

        for(int i=0;i<M-nS-1;i++)
            if(X[i].cost>X[i+1].cost)
            {
                sortat=0;

                aux=X[i];
                X[i]=X[i+1];
                X[i+1]=aux;
            }
        nS++;

    }while(!sortat);
}

void initializare(int N,int arbori[])
{
    for(int i=1;i<=N;i++)
        arbori[i]=i;
}

void Kruskal(int N,int M,muchie X[],muchie muchiiFol[],int &costMin)
{//Initializam "padurea de arbori"
    int arbori[Nmax/2+1];
    initializare(N,arbori);

    int nMFol=0;//numarul de muchii folosite
    int mA=0;//muchia acutala din vectorul X

    while(nMFol<N-1)//un arbore are N-1 muchii
    {
        if(arbori[X[mA].c1]!=arbori[X[mA].c2])//nu formam ciclu
        {
            muchiiFol[nMFol]=X[mA];
            nMFol++;

            costMin+=X[mA].cost;

        //intersectam cei 2 arbori
            int cul1=arbori[X[mA].c1];
            int cul2=arbori[X[mA].c2];

            for(int i=1;i<=N;i++)
                if(arbori[i]==cul1)
                    arbori[i]=cul2;
        }

        mA++;
    }
}

void afisare(int N,muchie mFol[],int costMinim)
{ofstream out("apm.out");
    out<<costMinim<<'\n'<<N-1<<'\n';

    for(int i=0;i<N-1;i++)
        out<<mFol[i].c1<<" "<<mFol[i].c2<<'\n';
out.close();
}

int main()
{
    int N,M;//noduri/muchii
    muchie X[Nmax];//muchiile
    citire(N,M,X);

//Sortam muchiile crescator dupa cost
    Bubble_Sort(M,X);

//APM
    muchie muchiiFolosite[Nmax/2];
    int costMinim=0;
    Kruskal(N,M,X,muchiiFolosite,costMinim);

    afisare(N,muchiiFolosite,costMinim);
    return 0;
}