#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 A[NMAX]; //retin indicii muchiilor selectate in apm

int tata[NMAX];
int h[NMAX]; //h[i]=inaltimea arborelui cu radacina i

int Find(int x);
void Union(int i, int j);
void creare_heap_inserare(int H[], int &n);
void afisare_heap(int H[], int n);
//void inserare(int H[NMAX], int& n, int x);
void combinare(int H[], int n, int i);
void creare_heap_combinare(int H[], int &n);
int ExtrageMin(int H[], int &n);
void afisare();
void citire();


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

int main()
{int i, nr=0, cx, cy, mmin;
 citire();
 creare_heap_combinare(H,m);
 //afisare_heap(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 inserare(int H[NMAX], int& n, int x)
//se insereaza valoare x in heapul H care are n elemente
{int fiu, tata;
 fiu=++n; tata=fiu>>1;
 while (tata && H[tata]>x)
 {
     H[fiu]=H[tata];
     fiu=tata;
     tata=fiu>>1;
 }
 H[fiu]=x;
}
*/
void afisare_heap(int H[], int n)
{   int i;

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


void combinare(int H[], 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], tata, fiu;
  tata=i; fiu=i<<1;
  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;
            }
            else //am gasit locul potrivit pentru x
            break;
        }
   H[tata]=x;
}

void creare_heap_combinare(int H[], 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[], 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 fiu al lui i
//i si j sunt radacinile arborilor care reprezinta cele doua multimi
{if (h[i]<h[j]) //i devine fiu 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);
}