#include<fstream>
#include<algorithm>
#define dmax 400003
#define nmax 200003
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n, m,nr,j,cost, sol[nmax], T[nmax], H[nmax];

struct muchie
{   int a,b,cost;} muchia[dmax];

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

void reuneste_arb(int a, int b)
{
    while(T[a]!=0)   a=T[a];
    while(T[b]!=0)   b=T[b];

    if(H[a] == H[b])
      { T[a] = b; H[b]++; }
    else if(H[a]<H[b])  T[a]=b;
         else  T[b]=a;
}
 bool verif(int a, int b)
   {

   while(T[a]!=0)   a=T[a];
    while(T[b]!=0)   b=T[b];
    return (a==b);
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
      f>>muchia[i].a>>muchia[i].b>>muchia[i].cost;
    sort(muchia+1, muchia+m+1, cmp);

    for(int i=1;i<=n;i++) H[i]=1;
    j=1; cost=0;
    while(nr<n-1)
    {
        while(verif(muchia[j].a, muchia[j].b)) j++;
        nr++;
        sol[nr] = j;
        cost+=muchia[j].cost;
        reuneste_arb(muchia[j].a, muchia[j].b);
    }
    g<<cost<<'\n';
    g<<n-1<<'\n';
    for(int i=1; i<n; i++)g<<muchia[sol[i]].a<<" "<<muchia[sol[i]].b<<'\n';
    return 0;
}