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

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int tata[NMAX];
int h[NMAX];
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;
Muchie H[NMAX],A[NMAX];
void citire(int &n,Muchie H[]);
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 x);
void Union(int x,int y);
int costtotal;
int nrsel;
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);
   }

}
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 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)
}