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

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;


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

bool cmpf (int ii, int jj)
{return(v[ii]<v[jj]);}

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);
   v[i]=zz;   
   x[i]=xx;
   y[i]=yy;
   IND[i]=i;
  }

for(i=1; i<=n; i++)
 {root[i]=i;
  size[i]=1;}  
  
sort(IND + 1,IND + m + 1,cmpf);
  
for(i=1; i<=m; i++)
  {if(find(x[IND[i]])!=find(y[IND[i]]))
    {unite(x[IND[i]],y[IND[i]]);
    sum+=v[IND[i]];
    counter++;
    xa[counter]=x[IND[i]];
    ya[counter]=y[IND[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;}