// APM

#include<fstream>
#include<vector>
#define Mmax 400001

using namespace std;

vector<int> APM;
int n, m, X[Mmax], Y[Mmax], C[Mmax], ind[Mmax], G[Mmax]; 

void citire()
{
     int i, x, y, c;
     ifstream f("apm.in");
        f>>n>>m;
        
     for(i=1;i<=m;i++)
      {
         f>>x>>y>>c;
         
         X[i]=x;
         Y[i]=y;
         C[i]=c;
         ind[i]=i;
      }

   f.close();
   
   for(i=1;i<=n;i++)
     G[i]=i;
       
}

bool cmp(int i, int j)
{
     return C[i]<C[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, j, 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+=C[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=1;i<n;i++)
      g<<X[ind[i]]<<" "<<Y[ind[i]]<<"\n";
      
    g.close();
      
    return 0;
}