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

#define Nmax 400001

vector<int> APM;
int n, m, x[Nmax], y[Nmax], cost[Nmax], ind[Nmax], G[Nmax];

void citire()
{
     int i;
     ifstream f("apm.in");
       f>>n>>m;
       
     for(i=1;i<=m;i++)
       {
         f>>x[i]>>y[i]>>cost[i];
         ind[i]=i;
       }
       
     f.close();
     
     for(i=1;i<=n;i++)
       G[i]=i;
 }

bool cmp(int i, int j)
{
   return (cost[i]<cost[j]);
}

int Padure(int i)
{
    if(G[i]==i)
       return i;
    G[i]=Padure(G[i]);
    
    return G[i];
}

void uneste(int i, int j)
{
     G[Padure(i)]=Padure(j);
 }

    
int main()
{
    int i, rez=0;
    citire();
    
    sort(ind+1, ind+m+1, cmp);
    
    for(i=1;i<=m;i++)
    {
      if(Padure(x[ind[i]])!=Padure(y[ind[i]]))
        { 
         rez=rez+cost[ind[i]];
         uneste(x[ind[i]], y[ind[i]]);
         APM.push_back(ind[i]);
        }
    }   
    
    ofstream g("apm.out");
       g<<rez<<"\n";
       g<<n-1<<"\n";
       
     for(i=0;i<n-1;i++)
       g<<x[APM[i]]<<" "<<y[APM[i]]<<"\n";
     g.close();
     
    return 0;
}