#include <fstream>
using namespace std;

ofstream fout("apm.out");

struct muchie
{
   int x,y,c;
};

muchie v[400001];

int n, m, s, a[400001], nr;
void citire();
void sort(int ,int );
void kruskal();
void afisare();
int main()
{
   citire();
   sort(1,m);
   kruskal();
   afisare();
}
void citire()
{
   ifstream fin("apm.in");
   fin>>n>>m;;
   int i,j,k;
   for(int z=1;z<=m;z++)
   {
      fin>>i>>j>>k;
      v[z].x=i;
      v[z].y=j;
      v[z].c=k;
   }
}
void sort(int st,int dr)
{
   if(st<dr)
   {
      int i=st,j=dr,d=0;
      while(i<j)
      {
         if(v[i].c>v[j].c)
         {
            muchie aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            d=1-d;
         }
         if(d==0)
            j--;
         else
            i++;
      }
      sort(st,i-1);
      sort(i+1,dr);
   }
}
void kruskal()
{
   int p[200001];
   for(int i=1;i<=n;i++)
      p[i]=i;
   for(int i=1;i<=m;i++)
      if(p[v[i].x]!=p[v[i].y])
      {
         s+=v[i].c;
         a[++nr]=i;
         int a,b;
         a=max(p[v[i].x],p[v[i].y]);
         b=min(p[v[i].x],p[v[i].y]);
         for(int j=1;j<=n;j++)
            if(p[j]==a)
               p[j]=b;
         
   }
}
void afisare()
{
   fout<<s;
   fout<<'\n';
   fout<<nr;
   fout<<'\n';
   for(int i=1;i<n;i++)
      fout<<v[a[i]].x<<" "<<v[a[i]].y<<"\n";

}