#include <cstdio>
#define NMAX 200001
#define MMAX 400001

using namespace std;
FILE *in, *o;
struct muchie{int x,y,c;}G[MMAX];
int n,m;
int H[MMAX];
int tata[MMAX];
int h[MMAX];
long long cost;
int A[NMAX];//indicii m selectate in apm

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

void Union(int i, int j)
{
    //i, j radacinile arborilor
    if(h[i]<h[j])
        tata[i]=j;
    else
    {
        tata[j]=i;
        if(h[i]==h[j])
            h[i]++;
    }
}
void citire()
{
    int i;
    in=fopen("apm.in","r");
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(in,"%d%d%d",&G[i].x,&G[i].y,&G[i].c);
    }
    fclose(in);
}

void comb(int H[],int n, int i)
{
    //se combina nodul H[i] cu heapurile cu radacinile 2i, 2i+1, obtinand un nou heap cu radacina H[i]
    int x=H[i], tata=i,fiu=i<<1;
    while(fiu<=n)
    {
        if(fiu+1<=n&&G[H[fiu+1]].c<G[H[fiu]].c)
            fiu++;
        //cel mai mic dintre fii
        if(G[H[fiu]].c<x)
        {
            H[tata]=H[fiu];
            tata=fiu;
            fiu=tata<<1;
        }
        else
            break;//am gasit locul
    }
    H[tata]=x;
}

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

int extractminim(int H[],int &n)
{
    int minim=H[1];
    H[1]=H[n--];
    comb(H,n,1);
    return minim;
}

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

int main()
{
    int nr=0,minim,cx,cy;
    //c_heap_ins(H,n);
    citire();
    c_heap_comb(H,m);
    while(nr<n-1)
    {
        minim=extractminim(H,m);
        cx=Find(G[minim].x);
        cy=Find(G[minim].y);
        if(cx!=cy)
        {
            nr++;
            A[nr]=minim;
            cost+=G[minim].c;
            Union(cx,cy);
        }
    }
    afisare();
    return 0;
}