#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct vector{
       short x,y,val,done;
       };

class FX{
public:
      void sort(int l, int r, vector *vectors)
       {

            int i,k;
            vector b;
            if (l>r) return;
            b = vectors[l]; k=l;
            for(i=l+1;i<=r;i++)
              if(vectors[i].val<b.val){
                                   k++;
                                   swap(vectors[k],vectors[i]);
                                   }
              vectors[l]=vectors[k];
              vectors[k]=b;
              sort(l,k-1,vectors);
              sort(k+1,r,vectors);
       }

      };

class Graf : public FX
{

public:
        int parents[200003],n,m,value,edges,sz[200003];
        vector vectors[200003];

       Graf(int n,int m)
       {


               for(int i=1;i<=n;i++) parents[i] = i;
               this->n = n;
               this->m = m;
               this->value = 0;
       }

       void Read()
       {
            for(int i=1;i<=m;i++) fin>>vectors[i].x>>vectors[i].y>>vectors[i].val;
       }
       void SortVectors()
       {
            sort(1,m,vectors);
       }

       void ShowVectors()
       {    
            ofstream vec("vectors.txt");
            for(int i=1;i<=m;i++) vec<<vectors[i].x<<" "<<vectors[i].y<<" "<<vectors[i].val<<endl;
            vec<<endl;
       }

       void ShowParents()
       {
            for(int i=1;i<=n;i++) cout<<parents[i]<<" ";
            cout<<endl;

       }
       int root(int i){
           while(i != parents[i]) {
                   parents[i] = parents[parents[i]];
                   i= parents[i];
                   
                   }
           return i;
       }
       void Union(int i, int j)
       {
            int p = root(i);
            int q = root(j);
            if(sz[p] < sz[q]){ parents[p] =q; sz[q] += sz[p]; }
            else             { parents[q]= p; sz[p] += sz[q]; }
       }

       bool Connected(int i, int j){
            return root(i) == root(j);
            }
            
       void Apm()
       {
            //while(nodes<n)
            for(int i=1;i<=m;i++){
                    int p = vectors[i].x;
                    int q = vectors[i].y;
                    if(!Connected(p,q)){
                                         Union(p,q);
                                         value += vectors[i].val;
                                         vectors[i].done = 1;
                                         edges++;
                                        // cout<<p<<" "<<q<<" "<<vectors[i].val<<endl;
                                         //ShowParents();
                                         //cout<<value<<endl;
                                         }
                    
                    
                   // system("pause");
                    }

       }

       void ShowResult()
       {
           fout<<value<<endl;
           fout<<edges<<endl;
           for(int i=1;i<=m;i++)
            if(vectors[i].done == 1) fout<<vectors[i].x<<" "<<vectors[i].y<<endl;

       }

      };

int n,i,k,j,m,ac=0,value=0;


int main(){
    fin>>n>>m;
    Graf *graf = new Graf(n,m);
    graf->Read();
    graf->SortVectors();

    //graf->ShowVectors();
    
    graf->Apm();
    graf->ShowResult();
    //system("pause");

}