/*Arbore partial de cost minim*/
   /*Krukskal*/

#include<stdio.h>
using namespace std;


int v[400001],x[400001],y[400001],counter;
int root[200001], size[200001];
int xa[200001], ya[200001];
long long sum;

int find(int g)
{int r;
 r=g;
 while(root[r]!=r)
    r=root[r];
 
 int q,p;
 q=g;
 while(root[q]!=q)
   {p=root[q];
    root[q]=r;
    q=p;}
  
 return r;}
 
void unite(int f, int g)
{int rf,rg;
 rf=find(f);
 rg=find(g);
 if(size[rf]>size[rg])
    root[rg]=root[rf];
 else
    root[rf]=root[rg];
 
 if(size[rf]==size[rg])
   size[rg]++;         
}  


int n,m,i,j;
int main()
{int xx,yy,zz,poz;
freopen("apm.in", "r", stdin);
freopen("apm.out", "w", stdout);
scanf("%d %d", &n, &m);
for(i=1; i<=m; i++)
  {scanf("%d %d %d", &xx, &yy, &zz);
   poz=i;
   while(poz>1 && v[poz-1]>zz)
     {v[poz]=v[poz-1];
      x[poz]=x[poz-1];
      y[poz]=y[poz-1];
      poz--;}
   v[poz]=zz;   
   x[poz]=xx;
   y[poz]=yy;
  }
for(i=1; i<=n; i++)
 {root[i]=i;
  size[i]=1;}  
  
for(i=1; i<=m; i++)
  {if(find(x[i])!=find(y[i]))
    {unite(x[i],y[i]);
    sum+=v[i];
    counter++;
    xa[counter]=x[i];
    ya[counter]=y[i];
    if (counter==(n-1))
      break;}  
  }    
printf("%d\n",sum);
printf("%d\n",n-1);
for(i=1; i<=n-1; i++)
 printf("%d %d\n",ya[i],xa[i]);
return 0;}