#include <fstream>
#define NMAX 200002
#define MMAX 400002

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, costtotal;
Muchie H[MMAX];
Muchie A[NMAX];
int tata[NMAX];
int h[NMAX]; ///h[i]=inaltimea arborelui cu radacina i

void creare();
void combinare(int n, Muchie H[], int poz);
Muchie extrageMin(int &n, Muchie H[]);
int Find (int x); ///returneaza radacina arborelui din care face parte x
void Union (int x, int y); ///reuneste arborele cu radacina x cu arborele cu radacina y

int main()
{Muchie mmin;
 int cx, cy, i;
 creare();
 while (nrsel<n-1)
        {
          mmin=extrageMin(m, H);
          cx=Find(mmin.x);
          cy=Find(mmin.y);
          if (cx!=cy)
             {
              nrsel++;
              A[nrsel]=mmin;
              costtotal+=mmin.cost;
              Union(cx,cy);
             }
        }
   //afisare
   fout<<costtotal<<'\n';
   fout<<n-1<<'\n';
   for (i=1; i<n; i++)
        fout<<A[i].x<<' '<<A[i].y<<'\n';
   fout.close();
   return 0;
}

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)
///returneaza radacina arborelui din care face parte x
{int rad, aux;
 rad=x;
 while (tata[rad]) rad=tata[rad];
 //compresia drumului
 while (tata[x])
       {
         aux=tata[x];
         tata[x]=rad;
         x=aux;
       }
 return rad;
}

void Union (int x, int y) ///reuneste arborele cu radacina x cu arborele cu radacina y
{
 if (h[x]<h[y]) tata[x]=y;
     else
     {tata[y]=x;
      if (h[x]==h[y]) h[x]++;
     }
 ///O(1)
}