#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std ;
 const int maxn=400100;
    int gr[maxn],x[maxn],y[maxn],cost[maxn];
      int n,m,rez,indice[maxn];
      
 vector <int> apm;
 int padure(int i)
 { 
     if(gr[i]==i) return i;
       gr[i]=padure(gr[i]);
        return gr[i];
          }
     void reuniune (int i,int j)
   {
        gr[padure(i)]=padure(j);     
 
 }
 bool cmp(int i, int j)
 {
   return (cost[i]<cost[j]);     
 }
 
 int main()
 {
                 freopen( "apm.in","r",stdin);
                 freopen ("apm.out","w",stdout);
                 scanf ("%d %d \n", &n ,&m );
 
     
   for(int i=1;i<=m;i++)
     {
                   scanf( "%d %d %d \n",&x[i],&y[i],&cost[i]);
                   indice[i]=i;
                   
     }  
    for(int i=1;i<=n;i++)
        gr[i]=i;
          sort(indice+1,indice+1+m,cmp);
     
     for(int i; i<=m; i++)
     {
     if(padure(x[indice[i]])!=padure(y[indice[i]]))
     {
     rez+=cost[indice[i]];
     reuniune(x[indice[i]],y[indice[i]]);
     apm.push_back(indice[i]);
                                                   
     }        
     }
     printf("%d \n",rez);
     printf("%d\n",n-1);
     for(int i=0;i<n-1;i++)
     printf("%d %d \n",x[apm[i]], y[apm[i]]);
     return 0;
     
 }