#include <cstdio>
#define NMAX 200001
#define MMAX 400001
//min heap
using namespace std;
struct Muchie {int x,y,c;}G[MMAX];
int n,m;
int H[MMAX];
long long int cost;
int tata[NMAX];
int h[NMAX];
//h[i]=inaltimea arborelui cu radacina i
int Find(int x);
void Union(int i, int j);
int A[NMAX];//retin indicii muchiilor selectate in apm
void afisare_heap(int H[NMAX],int n);
void combinare(int H[NMAX], int n, int i);
void creare_heap_combinare(int H[NMAX], int &n);
int ExtrageMin(int H[NMAX], int &n);
void afisare();
void citire();
FILE* fout=fopen("apm.out","w");
int main()
{   int nr=0,cx,cy,mmin;
    citire();
    creare_heap_combinare(H,m);
    while(nr<n-1)
    {
        mmin=ExtrageMin(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();
    return 0;
}

void combinare(int H[NMAX], int n, int i)
//se combina nodul H[i] cu heapurile cu radacinire
//2i si 2i+1 obtinand un heap cu rad H[i]
{
   int x=H[i],tata,fiu;
   tata=i; fiu=2*i;//sau fiu=<<i
   while(fiu<=n)//exista fiu stang
   {
       if(fiu+1<=n && G[H[fiu+1]].c<G[H[fiu]].c) fiu++;
       //fiu indica cel mai mic dintre fii
       if(G[H[fiu]].c<G[x].c)
       {
           H[tata]=H[fiu];
           tata=fiu;
           fiu=tata<<1;//sau fiu=tata*2
       }
       else //am gasit locul potrivit pentru x
       break;
   }
    H[tata]=x;
}

void creare_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);
}

int ExtrageMin(int H[NMAX], int &n)
{
    int minim=H[1];
    H[1]=H[n--];
    combinare(H,n,1);
    return minim;
}

void citire()
{
    int i;
    FILE * fin=fopen("apm.in", "r");
    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 Find(int x)
{
    //caut radacina
    int aux, rad=x;
    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)
//il fac pe j fiul al lui i
//i si j sunt radacinile arborilor care reprezinta cele 2 multimi
{
    if(h[i]<h[j]) //i devine fiul al lui j
    tata[i]=j;
    else
    {
        tata[j]=i;
        if(h[i]==h[j])
        h[i]++;
    }
}

void afisare()
{
    int i;
    fprintf(fout, "%d\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);
}