#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
    int x,y,cost;
}v[200100];

int compare (muchie A,muchie B)
{
    return (A.cost<B.cost);
}

int n,m,ct,t[200100],h[200100],sol[200100];



int rez(int X,int Y)
{
    int r1,x1,y1,r2,c;
  r1=X;r2=Y;
  while(t[r1]!=0)r1=t[r1];
  while(t[r2]!=0)r2=t[r2];

  if(r1==r2)return 0;

  while(t[X]!=0){x1=t[X];t[X]=r1;X=x1;}
  while(t[Y]!=0){y1=t[Y];t[Y]=r2;Y=y1;}


  if(h[r1]>h[r2]){t[r2]=r1;c=r1;}
  else {t[r1]=r2;c=r2;}

 if(h[r1]==h[r2])h[c]++;

   return 1;
}








void kruskal ()
{
    int i,k;
    i=1;
    k=0;
    ct=0;
    while(k<n-1)
    {
        if(rez(v[i].x,v[i].y))
        {
            k++;
            ct+=v[i].cost;
            sol[k]=i;
        }
        i++;
    }
}





int i;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].cost;
    sort(v+1,v+m+1,compare);


    for(i=1;i<=n;i++)
    {
        t[i]=0;
        h[i]=1;
    }

    kruskal();
    g<<ct<<'\n';
    g<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
    {
        g<<v[sol[i]].x<<" "<<v[sol[i]].y<<'\n';
    }
    return 0;
}