#include<fstream.h>

#define xn 200001
#define xm 400001

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

int a[xm],b[xm],c[xm],t[xn],rang[xn],r[xm][2],n,m,nr,cost;

int multime(int i)
{
    if(t[i]!=i)
       t[i]=multime(t[i]);
    return t[i];
}

void reuniune(int i,int j)
{
     i=multime(i);
     j=multime(j);
     
     if(i==j) return ;
     
     if(rang[i]<rang[j])
       t[i]=j;
     else
       t[j]=i;
     
     if(rang[i]==rang[j]) rang[i]++;
}

int poz(int li,int ls)
{
    int aux, i=0,j=-1;
    while(li<ls)
    {
      if(c[li]>c[ls])
      {
        aux=a[li]; a[li]=a[ls]; a[ls]=aux;
        aux=b[li]; b[li]=b[ls]; b[ls]=aux;
        aux=c[li]; c[li]=c[ls]; c[ls]=aux;
        aux=-i; i=-j; j=aux;
      }
      li+=i;
      ls+=j;
    }
    return li;
}

void qsort(int li,int ls)
{
     if(li<ls)
     {
       int k;
       k=poz(li,ls);
       qsort(li,k-1);
       qsort(k+1,ls);
     }
}

void kruskal()
{
     qsort(1,m);
     
     int i;
     
     for(i=1;i<=n;i++)
      t[i]=i;
     
     for(i=1;i<=m;i++)
     {
       if(multime(a[i])==multime(b[i])) continue;
       
       reuniune(a[i],b[i]);
       
       cost+=c[i];
       
       r[++nr][0]=a[i];
       r[nr][1]=b[i];
     }
}

int main()
{
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
      fin>>a[i]>>b[i]>>c[i];
    
    kruskal();
    
    fout<<cost<<'\n'<<nr<<'\n';
    for(i=1;i<=nr;i++)
     fout<<r[i][0]<<' '<<r[i][1]<<'\n';
    fout.close();
    return 0;
}