#include <fstream>
#define NMAX 200002
#define MMAX 400002
using namespace std;

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

struct Muchie{int x; int y; int  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,tata[NMAX],h[NMAX],nrsel,costtotal;
Muchie H[MMAX],A[NMAX];
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)
{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)
{
   if(h[x]<h[y]) tata[x]=y;
      else
      {tata[y]=x;
       if(h[x]==h[y])
          h[x]++;
      }
   //O(1);
}