#include <fstream>
#define NMAX 200000
#define MMAX 400000
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 tata[NMAX],nrcel,costtotal,m,cx,cy;
muchie a[NMAX],mmin;
int h[NMAX];
int Find(int x);
void Union(int x, int y);
int n;
muchie H[MMAX];
void creare();

void combinare(int n, muchie H[], int poz);
muchie extrageMin(int &n, muchie H[]);

int main()
{
    int i;
 // citire(n, H);
  creare();
  while(nrcel<n-1)
  {
      mmin=extrageMin(m,H);
      cx=Find(mmin.x);
      cy=Find(mmin.y);
      if(cy!=cx)
      {
          nrcel++;
          a[nrcel]=mmin;
          costtotal+=mmin.cost;
          Union(cx,cy);
      }
  }
  fout<<costtotal<<'\n'<<n-1<<'\n';
  for(i=1;i<=n-1;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 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=x;
    while(tata[rad])
    {
        rad=tata[rad];
    }
    //compresia
    int aux;
    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
        if(h[y]>h[x])
        tata[y]=x;
        else
        {
            tata[x]=y;
            h[y]++;
        }
    //o(1)
}