#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn=400100;


ifstream f("apm.in");
ofstream g("apm.out");
int gr[maxn],x[maxn],y[maxn],cost[maxn],indice[maxn];
int i,rez,n,m;
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()
{
    
    
    f>>n>>m;
   for(i=1;i<=m;i++)
   {
   f>>x[i]>>y[i]>>cost[i];
   indice[i]=i;     
   }
   
       
       for(i=1;i<=n;i++)
       gr[i]=i;
       
       sort(indice+1,indice+1+m,cmp);
       
       for(i=1;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]);                                              
                                                      
        }                 
       }
       
       g<<rez<<"\n"<<n-1<<"\n";
       for(i=0;i<n-1;i++)
                         g<<y[Apm[i]]<<" "<<x[Apm[i]]<<"\n";
                         
//                         g<<"\n";
                         return 0;
}