#include <fstream>
#include <algorithm>

#define NMAX 200005
#define MMAX 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
       int x,y,cost;
}a[MMAX];
int n,m;

int tata[NMAX],ind[NMAX];
void citire()
{ 
     f>>n>>m;

    for(int i=1;i<=m;i++)
    {
            f>>a[i].x>>a[i].y>>a[i].cost;

    }
     
}

bool cmp (muchie x,muchie y) 
{ 
     return (x.cost<y.cost); 
}

int rad(int x)
{
   int y ,z;
   for(y=tata[x]; y!=tata[y]; y=tata[y]); //determin radacina
   while(x!=tata[x]) //comprim drumurile
   { 
                                   z=tata[x];
                                   tata[x]=y;
                                   x=z;
   }
   return y;
}


int main()
{
 
     citire();
     sort(a+1,a+m+1,cmp);
     for(int i=1;i<=n; i++) tata[i]=i;
     int k=0,i=1,cost_min=0;
     while(k<n-1)
     {
                 int r1=rad(a[i].x), r2=rad(a[i].y);
                 if(r1!=r2)
                 {
                           k++;
                           cost_min+=a[i].cost;
                           ind[k]=i;
                           if(r1<r2) tata[r2]=r1;
                           else tata[r1]=r2;
                           
                 }
                 i++;
               
     }
    g<<cost_min<<endl;
    g<<k<<endl;
    for(int i=1; i<=k; ++i)
    g<<a[ind[i]].x<<" "<<a[ind[i]].y<<endl;
    return 0;
}