using namespace std;
#include<fstream>
struct nod
{
       int vf;
       int cost;
       nod*  next;
};
int n,m,*v,*t,*d,*h,*poz,nH,costmin;
nod*  G[200005];
void addarc(int,int,int);
void promoveaza(int);
void cerne(int);
int main()
{
    nod *p;
    int i,x,y,z,pmin;
    ifstream fin("apm.in");
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
                     fin>>x>>y>>z;
                     addarc(x,y,z);
                     addarc(y,x,z);
    }
    v=new int[n+1];
    t=new int[n+1];
    d=new int[n+1];
    h=new int[n+1];
    poz=new int[n+1];
    for(i=1;i<=n;++i)
    {
                     v[i]=0;
                     t[i]=-1;
                     d[i]=32767;
                     h[i]=i;
                     poz[i]=i;
    }
    nH=n;
    d[0]=32767;
    v[1]=1;
    t[1]=d[1]=0;
    h[1]=h[nH--];
    poz[h[1]]=1;
    cerne(1);
    for(p=G[1];p;p=p->next)
    {
                           d[p->vf]=p->cost;
                           t[p->vf]=1;
                           promoveaza(poz[p->vf]);
    }
    for(i=1;i<n;++i)
    {
                    pmin=h[1];
                    if(d[pmin]==32767)
                      break;
                    v[pmin]=1;
                    costmin+=d[pmin];
                    h[1]=h[nH--];
                    poz[h[1]]=1;
                    cerne(1);
                    for(p=G[pmin];p;p=p->next)
                       if(v[p->vf]==0)
                         if(d[p->vf]>p->cost)
                         {
                                                     d[p->vf]=p->cost;
                                                     t[p->vf]=pmin;
                                                     promoveaza(poz[p->vf]);
                         }
    }
    ofstream fout("apm.out");
    fout<<costmin<<'\n'<<n-1<<'\n';
    for(i=1;i<=n;++i)
       if(t[i])
         fout<<i<<' '<<t[i]<<'\n';
    return 0;
}
void addarc(int i,int j,int c)
{
     nod *p=new nod;
     p->vf=j;
     p->cost=c;
     p->next=G[i];
     G[i]=p;
}
void promoveaza(int k)
{
     int eh=0,i,aux;
     while(k/2 && eh==0)
     {
               i=k/2;
               if(d[h[i]]<=d[h[k]])
                 eh=1;
               else
               {
                   aux=h[i];
                   h[i]=h[k];
                   h[k]=aux;
                   poz[h[i]]=i;
                   poz[h[k]]=k;
                   k=i;
               }
     }
}
void cerne(int k)
{
     int eh=0,i,aux;
     while(2*k<=nH && eh==0)
     {
                  i=2*k;
                  if(i+1<=n)
                    if(d[h[i]]>d[h[i+1]])
                      ++i;
                  if(d[h[k]]<=d[h[i]])
                    eh=1;
                  else
                  {
                      aux=h[i];
                      h[i]=h[k];
                      h[k]=aux;
                      poz[h[i]]=i;
                      poz[h[k]]=k;
                      k=i;
                  }
     }
}