#include <fstream>
#include <algorithm>
#define maxn 200005

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
    int x,y;
    int cost;
}a[maxn],sol[maxn],aux;

int tata[maxn];
int n,m,radx,rady,COST;

bool comp(muchie x,muchie y)
{
    if(x.cost<y.cost) return 1;
    return 0;
}

int radacina(int x)
{
    if(x==tata[x]) return x;
    tata[x]=radacina(tata[x]);
    return tata[x];
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
      f>>a[i].x>>a[i].y>>a[i].cost;

    for(int i=1;i<=n;i++)
     tata[i]=i;

   sort(a+1,a+m+1,comp);

   int i=1;
   int p=0;

   while(p<n-1)
   {
       radx=radacina(a[i].x);
       rady=radacina(a[i].y);
       if(radx!=rady)
       {
           p++;
           COST+=a[i].cost;
           sol[p]=a[i];
           tata[radx]=rady;

       }
       i++;
   }

   g<<COST<<"\n"<<p<<"\n";
   for(int i=1;i<=p;i++)
     g<<sol[i].x<<" "<<sol[i].y<<"\n";
    return 0;
}