#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{ int x,y,cost;}v[400001];
int i,m,n,costmin,j,nr,ma,nrm,mi,x,y,mu[400001],t[400001],c[200001];
int cmp(const void* z, const void* w)
{muchie* a=(muchie*)z;
 muchie* b=(muchie*)w;
   if(a->cost >= b->cost)
        return 1;
   else
    return 0;
}


int main()
{ f>>n>>m;
  for(i=1;i<=m;++i)
     f>>v[i].x>>v[i].y>>v[i].cost;
qsort(v+1,m,sizeof(muchie),cmp);
 for(i=1;i<=m;++i)
    g<<v[i].cost<<' ';
    for(i=1;i<=n;++i)
        c[i]=i;
    nr=0;
    i=1;
    nrm=0;
    costmin=0;
    while(nr<n-1)
    {x=v[i].x;
    y=v[i].y;
     if(c[x]!=c[y])
     {if(c[x]>c[y])
        {ma=c[x];
         mi=c[y];
         }
         else
         {ma=c[y];
          mi=c[x];

         }
         for(j=1;j<=n;++j)
             if(c[j]==ma)
               c[j]=mi;
         costmin=costmin+v[i].cost;
         nr++;
         nrm++;
         mu[nrm]=y;
         nrm++;
         mu[nrm]=x;
     }
        i++;
    }
   g<<costmin<<'\n';
    g<<nr<<'\n';
  for(i=1;i<=nrm;i=i+2)
      g<<mu[i]<<' '<<mu[i+1]<<'\n';
    return 0;
}