/*Arbore partial de cost minim*/
   /*Prim*/

#include<fstream>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,i,viz[200001],heapsize,o;
int x[200001], y[200001],sum;
struct lista {int nod; int cost; lista* next;};
struct heap_element{int origin; int nod; int cost;};
heap_element h[400001];

lista* a[400001];
lista* q;

void add(int x, int y, int c)
{lista* q = new lista;
 q->nod=y;
 q->cost=c;
 q->next=a[x];
 a[x]=q;}  

void percolate(int s)
{
heap_element key=h[s];
while(s>1 && h[s/2].cost>key.cost)
 {h[s]=h[s/2];
  s=s/2;}
h[s]=key;   
}

void sink(int t)
{int son=1;
heap_element aux;
while(son)
 {son=0;
  if(2*t<=heapsize)
 {son=2*t;
  if(2*t+1<=heapsize && h[2*t+1].cost<h[2*t].cost)
    son=2*t+1;}
  if(son && h[son].cost<h[t].cost)        
      {aux=h[t];
       h[t]=h[son];
       h[son]=aux;
       t=son;}
  else 
    son=0;     
  }   
}

void afisare()
{g<<endl<<endl<<endl<<"               ************************** "<<endl;
 for(int psi=1; psi<=heapsize; psi++)
  g<<"Origin: "<<h[psi].origin<<"    Destination : "<<h[psi].nod<<"     Cost: "<<h[psi].cost<<endl;
 g<<endl; 
}

void list_stuff()
{while(q)
 {if(viz[q->nod]==0)
    {heapsize++;
     h[heapsize].cost=q->cost;
     h[heapsize].nod=q->nod;
     h[heapsize].origin=o;
     percolate(heapsize);}       
 q=q->next;}
 //afisare(); 
} 
 
int main()
{f>>n>>m;
int xx,yy,cc;
for(i=1; i<=m; i++)
  {f>>xx>>yy>>cc;
   add(xx,yy,cc);
   add(yy,xx,cc);}
    
heapsize=0;

int count=1;
o=1;
viz[1]=1;

 /*g<<"&&&&"<<endl;
 g<<"O: "<<o<<endl;
 g<<"&&&&"<<endl;  */   

while(count<n)
{ q=a[o];    
 list_stuff();
 x[count]=h[1].origin;   y[count]=h[1].nod;    sum+=h[1].cost;   viz[h[1].nod]=1;
 o=h[1].nod;
 while(viz[h[1].nod]==1)
 {
 h[1]=h[heapsize];
 heapsize--;
 sink(1);}
 
 count++;}
 
 g<<sum<<endl;
 g<<n-1<<endl;
 for(i=1; i<=n-1; i++)
 g<<x[i]<<" "<<y[i]<<endl;   
 
return 0;}