#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 afisare(int n, Muchie H[]);
void inserare(int &n,Muchie H[], Muchie x);
void combinare(int n,Muchie H[],int poz);
Muchie extragereMin(int &n,Muchie H[]);
int Find(int x);///returneaza radadcina arborelui din care face parte x
void Union(int x,int y);///reuneste arborii x si y

int main()
{
 int cx,cy,i;
 Muchie mmin;
 creare();
 while (nrsel<n-1)
     {
      mmin=extragereMin(m,H);
      cx=Find(mmin.x);
      cy=Find(mmin.y);
      if (cx!=cy)
          {
           nrsel++;
           A[nrsel]=mmin;
           costtotal+=mmin.cost;
           Union(cx,cy);
          }
     }
 fout<<costtotal<<'\n';
 fout<<n-1<<'\n';
 for(i=1;i<n;i++)
    fout<<A[i].x<<' '<<A[i].y<<'\n';
 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 extragereMin(int &n,Muchie H[])
{
 Muchie minim;
 minim=H[1];
 H[1]=H[n--];
 combinare(n,H,1);
 return minim;
}
int Find (int x) ///O(n)
{
 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)///O(1)
{
 if (h[x]<h[y]) tata[x]=y;
     else
         {
          tata[y]=x;
          if (h[x]==h[y])
              h[x]++;
         }
}