#include <iostream>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream go("apm.out");
int n,m;
struct muchie
{
    int x,y,cost;
}g[100];
int a[100],c[100];
void init()
{
    int i;
    f>>n;
    f>>m;
    for(i=1;i<=m;i++)
        f>>g[i].x>>g[i].y>>g[i].cost;
    for(i=1;i<=n;i++) c[i]=i;
}
void afisare()
{
  int i,costa=0;

  for(i=1;i<n;i++)
  {
      costa+=g[a[i]].cost;

  }
  go<<costa<<"\n";
  go<<n-1<<"\n";

    for(i=1;i<n;i++)
  {
      go<<g[a[i]].x<<" "<<g[a[i]].y<<"\n";
  }

}
void sortare_muchii()
{
    int i,j;
    muchie aux;
    for(i=1;i<m;i++)
        for(j=i+1;j<=m;j++)
        {
            if(g[i].cost>g[j].cost)
            {
                aux=g[i];
                g[i]=g[j];
                g[j]=aux;
            }
        }
}
int main()
{
   int i,j,mini,maxi,nr;
   init();
   sortare_muchii();
   nr=0;
   for(i=1;nr<n-1;i++)
    if(c[g[i].x]!=c[g[i].y])
   {
       a[++nr]=i;
       if(c[g[i].x]<c[g[i].y])
       {
           mini=c[g[i].x];
           maxi=c[g[i].y];
       }
       else
       {
           mini=c[g[i].y];
           maxi=c[g[i].x];
       }
       for(j=1;j<=n;j++)
        if(c[j]==maxi) c[j]=mini;
   }
   afisare();
}