//Kruskal cu union-find si min-heap
#include <fstream>
#include <algorithm>
#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;


bool cmp(Muchie a,Muchie b)
{
    return a.cost<b.cost;
}

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

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

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,find1,find2;
    for(int i=1;i<=m&&nrSel<n;i++)
    {
        find1=Find(M[i].e1);
        find2=Find(M[i].e2);

        if(find1!=find2)
            {
                Union(find1,find2);
                muchiiSel[nrSel++]=i;
                AMPCost+=M[i].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;
}