#include <fstream>
#include <iostream>
#define NMAX 2000005
#define MMAX 4000005

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct Muchie
{
 int x,y,cost;
 friend bool operator < (Muchie a,Muchie b);
 friend bool operator > (Muchie a,Muchie b);
 friend bool operator <= (Muchie a,Muchie b);
 friend bool operator >= (Muchie a,Muchie b);
};

 bool operator < (Muchie a,Muchie b)
 {return a.cost<b.cost;}
 bool operator > (Muchie a,Muchie b)
 {return a.cost<b.cost;}
 bool operator >= (Muchie a,Muchie b)
 {return a.cost<b.cost;}
 bool operator <= (Muchie a,Muchie b)
 {return a.cost<b.cost;}

int n,m,nrsel,cx,cy,costmin,i;
int Tata[NMAX];
int Nivel[NMAX];
Muchie H[MMAX],mmin;
Muchie A[NMAX];
void creare();
void afisare(int n, Muchie H[]);
void inserare(int& n, Muchie H[], Muchie x);
void combinare(int n, Muchie H[], int poz);
Muchie extrageMin(int &n, Muchie H[]);
int Find(int);
void Union(int,int);

int main()
{
 creare();
 while (nrsel<n-1)
 {
  mmin=extrageMin(m,H);
  cx=Find(mmin.x);
  cy=Find(mmin.y);
  if (cx!=cy)
  {
   nrsel++;
   A[nrsel]=mmin;
   costmin+=mmin.cost;
   Union(cx,cy);
  }
 }
 fout<<costmin<<"\n";
 fout<<n-1<<"\n";
 for (i=1;i<n;i++)
  fout<<A[i].y<<" "<<A[i].x<<"\n";
}

void afisare(int n, int H[])
{int i;
 for (i=1; i<=n; i++) fout<<H[i]<<' ';
 fout<<'\n';
}

void inserare(int& n, int H[], int x)
{int tata, fiu;
 fiu=++n; tata=fiu/2;
 while (tata && H[tata]>x)
       {
         H[fiu]=H[tata];
         fiu=tata;
         tata=fiu/2;
       }
 H[fiu]=x;
}


void combinare(int n, Muchie H[], int poz)
{Muchie x=H[poz];
 int fiu, tata;
 tata=poz;
 fiu=2*tata;
 while (fiu<=n)
       {
         if (fiu+1<=n && H[fiu+1]<H[fiu]) fiu++;
         if (x <= H[fiu]) break;
         H[tata]=H[fiu];
         tata=fiu;
         fiu=2*tata;
        }
  H[tata]=x;
}

void creare()
{int i;
 fin>>n>>m;
 for (i=1; i<=m; i++) fin>>H[i].x>>H[i].y>>H[i].cost;
 for (i=m/2; i>0; i--)
     combinare(m, H, i);
}

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

int Find(int x)
{
 int q;
 if (Tata[x]==0)
  return x;
 else
 {
  q=Find(Tata[x]);
  Tata[x]=q;
  return q;
 }
}

void Union(int X1,int X2)
{
 if (Nivel[X1]>Nivel[X2])
  Tata[X2]=X1;
 else if (Nivel[X1]<Nivel[X2])
  Tata[X1]=X2;
 else
 {
  if (X1>X2)
  {
   Tata[X1]=X2;
   Nivel[X2]++;
  }
  else
  {
   Tata[X2]=X1;
   Nivel[X1]++;
  }
 }
}