#include<cstdio>
#include<algorithm>
#include<fstream>

using namespace std;

const int NMAX = 200001;
const int MMAX = 400001;

struct graf
{
    int x,y,c;

    void initializare(int _x,int _y,int _c)
    {
        x = _x;
        y = _y;
        c = _c;
    }

    bool operator()(const graf &A,const graf &B)
    {
        return A.c<B.c;
    }
};

void citire(),Krushkal(),afisare();

int N,M,cost_grag;
graf E[MMAX];
int Muchii[NMAX];

int Tata[NMAX];
int Inaltime[NMAX];

int Caut_tata(int x)
{
    if(Tata[x]!=x) Tata[x]=Caut_tata(Tata[x]);
    return Tata[x];
}

void adaug(int x,int y)
{
    if(Inaltime[x]<Inaltime[y])
    {
        Tata[x]=y;
        return;
    }
    if(Inaltime[x]>Inaltime[y])
    {
        Tata[y]=x;
        return;
    }
    Tata[x]=y;
    Inaltime[y]++;
}

void citire()
{
    int i,x,y,c;

    ifstream f("apm.in");
    f>>N>>M;

    for(i =1;i<= M;i++)
    {
        f>>x>>y>>c;
        E[i].initializare(x,y,c);
    }
}

void Krushkal()
{
    int i,j,x,y,c;

    sort(E+1,E+M+1,graf());

    for(i = 1;i<=N;i++)
        Tata[i]=i;

    for(i=1,j=0;i<=M && j<=N-1;i++)
    {
        x=E[i].x;
        y=E[i].y;
        c=E[i].c;

        if(Caut_tata(x) == Caut_tata(y)) continue;

        adaug(Caut_tata(x),Caut_tata(y));
        cost_grag+=c;
        Muchii[++j]=i;
    }
}

void afisare()
{
    int i;
    ofstream f("apm.out");
    f<<cost_grag<<endl;f.flush();
    f<<N-1<<endl;f.flush();
    for(i=1;i<=N-1;i++)
        f<<E[Muchii[i]].y<<" "<<E[Muchii[i]].x<<endl;
        f.flush();
}

int main()
{
    citire();
    Krushkal();
    afisare();
    return 0;
}