#include <cstdio>
#define MMAX 200003
#define NMAX 400005
//min heap
using namespace std;

FILE* fin=fopen("apm.in","r");
FILE* fout=fopen("apm.out","w");

void afisare_heap(int [], int);
void combinare(int [],int,int);
void crearea_heap_combinare(int [], int&);
int extrage_minim(int H[NMAX],int &n);
void citire();
void afisare();

int n,H[NMAX],m,h[NMAX];
long long cost=0;
int A[NMAX],tata[NMAX]; // retin indicii muchiilor selectate in APM
struct Muchie {int x,y,c;} G[MMAX];
int Find(int x);
void Union(int i,int j);

int main()
{
    int cx,cy,nr=0,mmin;
    citire();
    crearea_heap_combinare(H,m);
   // afisare_heap(H,m);
    while(nr<n-1)
    {
        mmin=extrage_minim(H,m);
        cx=Find(G[mmin].x);
        cy=Find(G[mmin].y);
        if(cx!=cy)
        {
            nr++;
            A[nr]=mmin;
            cost+=G[mmin].c;
            Union(cx,cy);
        }
    }
    afisare();
    fclose(fout);
    return 0;
}

void afisare()
{
    int i;
    fprintf(fout,"%lld\n",cost);
    fprintf(fout,"%d\n",n-1);
    for(i=1;i<n;i++)
    {
        fprintf(fout,"%d %d\n",G[A[i]].x,G[A[i]].y);
    }
    fclose(fout);
}

void Union(int i,int j)//i,j sunt radacinile arborilor
{//j fiu al lui i
    if(h[i]<h[j])
        tata[i]=j;
    else if(h[i]>h[j])
        tata[j]=i;
    else //daca is egale
    {
        h[i]++;
        tata[j]=i;
    }
}

int Find(int x)
{
    int rad=x,aux;
    while(tata[rad])
        rad=tata[rad];
    while(tata[x])
    {
        aux=tata[x];
        tata[x]=rad;
        x=aux;
    }
    return rad;
}


void citire()
{
    int i;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d%d",&G[i].x,&G[i].y,&G[i].c);
    }
}


int extrage_minim(int H[NMAX],int &n)
{
    int minim;
    minim=H[1];


    H[1]=H[n];
    n--;
    combinare(H,n,1);
    return minim;
}

void crearea_heap_combinare(int H[NMAX], int&n)
{
    int i;
    for(i=1;i<=n;i++) H[i]=i;
    for(i=n/2;i>0;i--) combinare(H,n,i);
}


void combinare(int H[NMAX],int n,int i)
{
    //se combina nodul H[i] cu heapurile cu radacinile 2i si 2i+1 obtinand un nou heap cu radacina H[i]
    int x=H[i];//valoare care coboara
    int tata,fiu;
    tata=i;
    //fiu=2*i;
    fiu= i<<1;
    while(fiu<=n)
    {
        if(fiu+1 <= n && G[H[fiu+1]].c < G[H[fiu]].c) fiu++;
        //fiu indica cel mai mic dintre fi
        if(G[H[fiu]].c<G[x].c)
        {
            H[tata]=H[fiu];
            tata=fiu;
            //fiu=tata*2;
            fiu= tata<<1;
        }
        else break;//ma opresc cand am gasit locul potrivit pt x
    }
    H[tata]=x;
}

void afisare_heap(int H[NMAX],int n)
{
    int i;

    for(i=1;i<=n;i++)
        fprintf(fout,"%d %d %d\n\n", G[H[i]].x,G[H[i]].y,G[H[i]].c);
    fprintf(fout,"\n");
}