#include <fstream>
#include <algorithm>
#define nmax 400001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
int t[nmax],h[nmax]={1};
int scos,nrmsel;

struct muchie
{ int x,y;
  float c;};

muchie a[nmax],b[nmax];

int Find(int x)
{
    while(t[x]!=0) x=t[x];
    return x;
}

void Union(int i, int j)
{
    if(h[i]>h[j]) t[j]=i;
    else
    { t[i]=j;
      if(h[i]==h[j]) h[j]++;
    }
}

void cit()
{int  i;
 int p1,p2,p3;
 fin>>n>>m;
 for(i=1;i<=m;++i)
    {fin>>p1>>p2>>p3;
     a[i].x=p1; a[i].y=p2; a[i].c=p3;
    }
}


void kruskal()
{int i=1;
 int v1,v2,x1,x2;
 while(nrmsel<n-1)
 { v1=a[i].x; v2=a[i].y;
   x1=Find(v1); x2=Find(v2);
   if(x1!=x2)
    { nrmsel++;
      b[nrmsel].x=v1; b[nrmsel].y=v2;
      scos+=a[i].c;
      Union(x1,x2);}
    i++;
 }}
int comp(muchie a, muchie b)
{
    if(a.c<b.c) return 1;
    return 0;
}

int main()
{   cit();
    sort(a+1,a+m+1,comp);
    kruskal();
    fout<<scos<<"\n";
    fout<<n-1<<"\n";
    for(int i=1;i<=nrmsel;i++)
        fout<<b[i].x<<" "<<b[i].y<<"\n";
    return 0;
}