#include <bits/stdc++.h>
#define NMAX 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
pair <int, int> P[NMAX];
int k,n,m,total,tata[NMAX/2];
int rang[NMAX/2];
struct muchie
{ int x;
  int y;
  int cost;
}v[NMAX];
bool cmp(muchie a, muchie b)
{ return a.cost<b.cost;

}
int caut_tata(int nod)
{ while(tata[nod]!=nod)
    nod=tata[nod];
 return nod;
}
void unire(int x, int y)
{ if(rang[x]<rang[y]) tata[x]=y;
  if(rang[x]>rang[y]) tata[y]=x;
  if(rang[x]==rang[y]) { tata[x]=y;
                          rang[y]++;
                        }
}
void APM()
{ for(int i=1;i<=m;i++)
    { int t1=caut_tata(v[i].x);
      int t2=caut_tata(v[i].y);
      if(t1!=t2)
      { unire(t1,t2);
        P[++k].first=v[i].x;
        P[k].second=v[i].y;
        total+=v[i].cost;
      }
    }
}
int main()
{ f>>n>>m;
  for(int i=1;i<=n;i++)
  { tata[i]=i;
    rang[i]=1;
  }
  for(int i=1;i<=m;i++)
    f>>v[i].x>>v[i].y>>v[i].cost;
  sort(v+1,v+m+1,cmp);
  APM();
  g<<total<<'\n';
  g<<n-1<<'\n';
  for(int i=1;i<=n-1;i++)
    g<<P[i].first<<" "<<P[i].second<<'\n';
    return 0;
}