#include <iostream>
#include <fstream>
using namespace std;
const int MAX=200001;
const int INF=10000;
int h[MAX],poz[MAX],nh,nr,v[MAX],vf[MAX],urm[2*MAX],lst[2*MAX],cst[MAX],d[MAX],st,dr,pret,pred[MAX],n,m;
long long cost=0;
bool sel[MAX];

ifstream in("apm.in");
ofstream out("apm.out");

void schimb(int p, int q)
{
   swap(h[p],h[q]);
   poz[h[p]]=p;
   poz[h[q]]=q;

}

void urca(int p)
{
    while(p>1 && d[h[p]]<d[h[p/2]])
    {
        schimb(p,p/2);
        p/=2;
    }
}

void adauga(int x)
{
    h[++nh]=x;
    poz[x]=nh;
    urca(nh);

}

void coboara(int p)
{
     int fs=2*p,fd=2*p+1,bun=p;
     if(fs<=nh && d[h[fs]]<d[h[bun]]) bun=fs;
     if(fd<=nh && d[h[fd]]<d[h[bun]]) bun=fd;
     if(bun!=p)
     {
         schimb(p,bun);
         coboara(bun);
     }

}

void sterge(int p)
{
   schimb(p,nh--);
   urca(p);
   coboara(p);
}

void adauga_muchie(int x, int y, int c)
{
     vf[++nr]=y;
     cst[nr]=c;
     urm[nr]=lst[x];
     lst[x]=nr;

}

void prim()
{
   int x,y,c;
   for(int i=2;i<=n;i++)
   {
      d[i]=INF;
      adauga(i);
   }

   d[1]=0;
   adauga(1);
   while(nh>0)
   {
       x=h[1];
       sterge(1);
       sel[x]=true;
       cost+=d[x];
       for(int p=lst[x];p!=0;p=urm[p])
       {
            y=vf[p];
            c=cst[p];
            if(c<d[y] && !sel[y])
            {
                d[y]=c;
                pred[y]=x;
                urca(poz[y]);
            }
       }

   }
}
int main()
{
     in>>n>>m;
     for(int i=1;i<=m;i++)
     {
         in>>st>>dr>>pret;
         adauga_muchie(st,dr,pret);
         adauga_muchie(dr,st,pret);

     }

     prim();
     out<<cost<<"\n";
     out<<n-1<<"\n";
     for(int i=2;i<=n;i++) out<<i<<" "<<pred[i]<<"\n";

    return 0;
}