#include<stdio.h>  
    #include<algorithm>  
    using namespace std;  
      
    struct muchie{int a,b,c;}v[400004];  
      
    int sol[400002];  
    int i,p,k,cost=0,m,n,nr[200002],tip[200040],urm[200040],ult[200040];  
      
   int cmp(muchie a,muchie b){  
     
   return a.c<b.c;}  
     
   void merge(int a,int b){  
   urm[ult[a]]=b;  
   nr[a]+=nr[b];
   ult[a]=ult[b];  
   int p=b;  
   do{tip[p]=a;  
   p=urm[p];  
   }while(p);  
   }  
     
   int main(){  
     
   freopen("apm.in","r",stdin);  
   freopen("apm.out","w",stdout);  
   scanf("%d %d",&n,&m);  
     
   for(i=1;i<=n;i++)  
           {tip[i]=i;  
           ult[i]=i;  
           nr[i]=1;  
           }  
     
   for(i=1;i<=m;i++)  
           scanf("%d %d %d",&v[i].a,&v[i].b,&v[i].c);  
     
   sort(v+1,v+1+m,cmp);  
     
   for(i=1;i<=m;i++)  
           if(tip[v[i].a]!=tip[v[i].b])  
                   {cost+=v[i].c;  
                   k++;  
                   sol[k]=i;  
                   if(nr[tip[v[i].a]]<nr[tip[v[i].b]])  
                   merge(tip[v[i].a],tip[v[i].b]);  
                   else  
                   merge(tip[v[i].b],tip[v[i].a]);}  
     
   printf("%d\n%d\n",cost,k);  
     
   for(i=1;i<=k;i++)  
           printf("%d %d\n",v[sol[i]].a,v[sol[i]].b);  
     
   return  0;}