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

struct muchie
{ int a;
  int b;
  int cost;
   bool operator<(const muchie& l)const
   {
       if(l.a==a){return l.b<b;}
        return l.a<a;
    }
 bool operator==(const muchie& l)const{
        return (l.a==a && l.b==b);
    }

};

int comp(const void *a, const void *b)
{ return ((muchie *)a)->cost-((muchie *)b)->cost; }

vector<int>multimi;
vector<muchie>vect_muchii;
set<muchie>cost_calcul;

int gaseste(int a)
{ if(multimi[a]==0) return a;
 return  multimi[a] = gaseste(multimi[a]);
}

void uniune(int a, int b)
{ multimi[a]=b;
}

void alg_kruskal(int nr_nod,int nr_muchii)
{   int i,j=0;

    for(i=0;i<=nr_nod;i++)
        multimi.push_back(0);

    qsort(&vect_muchii[0],nr_muchii,sizeof(muchie),comp);

  muchie temp;
    i=0;
   while(i<nr_nod-1)
    {  temp=vect_muchii[j];
       int m1,m2;
       m1=gaseste(temp.a);
       m2=gaseste(temp.b);
       if(m1!=m2)
       {
           cost_calcul.insert(temp);
           uniune(m1,m2);
          i++;
       }
        j++;
    }
}

int main()
{ fstream f("apm.in",ios::in);
  int i,n,m;
  f>>n>>m;

   for(i=0;i<m;i++)
   { muchie x;
     f>>x.a>>x.b>>x.cost;
    vect_muchii.push_back(x);
   }f.close();
fstream g("apm.out",ios::out);
   alg_kruskal(n,m);
   int total_cost=0;
   set<muchie>:: iterator it;
   for(it=cost_calcul.begin();it!=cost_calcul.end();it++)
     total_cost=total_cost+it->cost;
   g<<total_cost<<"\n";
     g<<n-1<<"\n";
for(it=cost_calcul.begin();it!=cost_calcul.end();it++)
     g<<it->a<<" "<<it->b<<" "<<endl;
    return 0;
}