/*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],count,heapsize,o;
int x[200001], y[200001],sum;
int pozit;
struct lista {int nod; int cost; lista* next;};
struct heap_element{int origin; int nod; int cost;};
heap_element h[400001];

lista* a[400001];

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

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);}
int count;    
count=1;
viz[1]=1;
heapsize=1;
h[1].nod=1;
h[1].cost=0;
lista* q;
while(count<n)
{do
 {q = a[h[1].nod];
 o=h[1].nod;
 h[1]=h[heapsize];
 heapsize--;
  if(heapsize)
   sink(1);} while(heapsize>0 && viz[h[1].nod]==1);

 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;} 
 x[count]=h[1].origin;
 y[count]=h[1].nod;  
 sum+=h[1].cost;
 viz[h[1].nod]=1;
 afisare();
 count++;}
 
 g<<sum<<endl;
 for(i=1; i<=n-1; i++)
 g<<x[i]<<" "<<y[i]<<endl;   
 
return 0;}