#include<fstream>
using namespace std;
ofstream fout("apm.out");
struct muchie
{
   int x,y,c;
};
muchie v[400001];
int n,m,s,index[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.c>v[j].c)
         {
            muchie  aux=v;
            v=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;
   for(int i=1;i<=m;i++)
      if(p[v.x]!=p[v.y])
      {
         s+=v.c;
         index[++nr]=i;
         int a,b;
         a=max(p[v.x],p[v.y]);
         b=min(p[v.x],p[v.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[index].x<<" "<<v[index].y<<"\n";

}