#include<fstream>
#include<cstring>
#include<algorithm>
#define nmax 211206
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
struct muchie
{
    int x,y,cost;
}v[nmax];
bool cmp(muchie a,muchie b)
{
    return a.cost<b.cost;
}
int i,j,n,m,cer,cate,arbore[nmax],a,b,rasp1,apm,euri,blocati;
struct ala
{
    int x,y;
}r[nmax];
int main ()
{
 f>>n>>m;
 while(m)
 {
     m--;
     cate++;
    f>>v[cate].x>>v[cate].y>>v[cate].cost;
 }
 sort(v+1,v+cate+1,cmp);
 for(i=1;i<=n;i++)
     arbore[i]=i;
 int nrv=1;
     for(i=1;nrv<=n-1;i++)
     {
         a=v[i].x,b=v[i].y;
         if(arbore[a]!=arbore[b])
         {
          r[nrv].x=a;
          r[nrv].y=b;
          apm+=v[i].cost;
          nrv++;
        int  maxim=max(arbore[a],arbore[b]);
        int  minim=min(arbore[a],arbore[b]);
         for(j=1;j<=n;j++)
             if(arbore[j]==maxim)
                 arbore[j]=minim;
         }
     }
 g<<apm<<"\n"<<n-1<<"\n";
 for(i=1;i<nrv;i++)
      g<<r[i].x<<" "<<r[i].y<<"\n";
}