//Kruskal cu union-find si min-heap
#include <fstream>
#define MMax 400001
#define NMax 200001

using namespace std;

fstream fin("apm.in",ios::in);
fstream fout("apm.out",ios::out);

struct Muchie{int e1,e2,cost;};

Muchie M[MMax];//le voi organiza ca min heap
int C[NMax],H[NMax],n,m,nrSel;//C - se considera multimile
                    //H - inaltimile fiecare arbore(arbore care rep o multime)
int muchiiSel[NMax];
long long AMPCost=0;

inline int left_son(int k){return 2*k;}
inline int right_son(int k){return 2*k+1;}
inline int father(int k){return k/2;}

void downHeap(int k)
{
    int son;
    do
    {
        son=0;
        if(left_son(k)<=m)
        {
            son=left_son(k);
            if(right_son(k)<=m&&M[right_son(k)].cost<M[left_son(k)].cost)
                son=right_son(k);
            if(M[son].cost>M[k].cost) son=0;
        }

        if(son)
        {
            swap(M[son],M[k]);
            k=son;
        }
    }while(son);
}

void BuildMinHeap()
{
    int i;
    for(i=m/2;i>0;--i)
        downHeap(i);
}

Muchie ExtractMin()
{
    Muchie min=M[1];
    swap(M[1],M[m]);
    m--;
    downHeap(1);
    return min;
}

void Read()
{
    int i;
    fin>>n>>m;

    for(i=1;i<=m;i++)
    {
        fin>>M[i].e1>>M[i].e2>>M[i].cost;
    }
    BuildMinHeap();
}

void Union(int x,int y)
{
    if(H[x]>H[y]) C[y]=x;
    else
    {
        C[x]=y;
        if(H[x]==H[y]) H[y]++;
    }
}

int Find(int x)
{
    int r=x;
//determin radacina arborelui
    while(C[r]) r=C[r];

    int y=x,t;
//comprim drumul de la x la radacina
    while(y!=r)
    {
        t=C[y];
        C[y]=r;
        y=t;
    }


    return r;
}

void Kruskal()
{
    int nrSel=1;
    Muchie min;
    while(nrSel<n)
    {
        min=ExtractMin();
        if(Find(min.e1)!=Find(min.e2))
            {
                Union(min.e1,min.e2);
                muchiiSel[nrSel]=m+1;
                nrSel++;
                AMPCost+=min.cost;
            }
    }
}

void Write()
{
    fout<<AMPCost<<endl;
    fout<<n-1;
    for(int i=1;i<n;i++)
        fout<<endl<<M[muchiiSel[i]].e1<<" "<<M[muchiiSel[i]].e2;
}

int main()
{
    Read();
    Kruskal();
    Write();

    return 0;
}