#include <fstream>
#include <algorithm>
#include <vector>

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

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

int rad(int x)
{
   while(tata[x]!=x)x=tata[x];
   return x;
}


int main()
{
 
    f>>n>>m;

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

    }
     sort(a+1,a+m+1,cmp);
     for(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);
                 int 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(i=1; i<=k; i++)
    g<<a[ind[i]].x<<" "<<a[ind[i]].y<<endl;
    return 0;
}