#include <fstream>  
    #define MAX 200000  
    using namespace std;  
      
      
    int n, m;  
    struct muchie{  
        int v1, v2;  
        int val;  
   };  
     
   muchie a[MAX];  
   muchie arb[MAX];  
   int p[MAX];  
   int h[MAX];  
   int cost;  
     
     
  ifstream fin("apm.in");  
   ofstream fout("apm.out");  
   void Read();  
   void Sort(int ,int);  
   void Init();  
   int Cauta(int);  
   void Unire(int, int);  
   void Afis();  
   void Kruskal();  
     
     
   
     
   
   int main()  
   {  
       Read();  
      Kruskal();  
       Afis();  
        
         
       fin.close();  
       fout.close();  
       return 0;  
   }  
     
   void Read()  
   {  
      fin >> n;  
       fin >> m;  
       for (int i = 1; i<=m; i++)  
       {  
          fin >> a[i].v1;  
           fin >> a[i].v2;  
           fin >> a[i].val;  
       }  
   }  
     
   void sort(int x,int y)    
   {    int i,j,p;    
        muchie aux;    
        if(x<y)    
         {  i=x-1;    
        j=y+1;    
        p=a[(x+y)/2].val;    
        while(i<j)    
        {   do i++; while(a[i].val<p);    
            do j--; while(a[j].val>p);    
            if(i<j) {  aux=a[i];    
                   a[i]=a[j];    
                   a[j]=aux;    
                }    
        }    
       sort(x,i-1);    
        sort(j+1,y);    
         }    
   }    
     
   void Init()  
   {  
       for (int i = 1; i<=n; i++)  
       {  
           p[i] = i;  
           h[i] = 0;  
       }  
   }  
     
   void Unire(int x, int y)  
   {  
       if (h[x] > h[y])  
      {  
           p[y] = x;  
       }  
       else  
       {  
         p[x] = y;  
           if (h[x] == h[y]) ++h[y];  
       }  
   }  
     
   int Cauta(int x)  
  {  
    if (x != p[x]) p[x] = Cauta(p[x]);  
      return p[x];  
  }  
    
  void Kruskal()  
  {  
      sort(1,m);  
      int k = 0;  
     Init();  
       
      for (int i = 1; i <= m; i++)  
      {  
          int r1 = Cauta(a[i].v1);  
          int r2 = Cauta(a[i].v2);  
         //fout << a[i].v1 << " " << a[i].v2 << "\n";  
          if (r1 != r2)  
          {  
              cost += a[i].val;  
              arb[++k] = a[i];  
              Unire(r1, r2);  
             if (k == n-1) break;  
          }  
      }  
  }  
    
  void Afis()  
  {  
      fout << cost << "\n";  
      fout << n-1 << "\n";  
      for (int i = 1; i <= n-1; i++)  
      {  
          fout << arb[i].v1 << " " << arb[i].v2 << "\n";  
      }  
  }