#include <vector>
#include <fstream>
using namespace std;
#define nmax 200001
#define mmax 400001
ifstream f("apm.in");
ofstream g("apm.out");
int t[nmax],n,m,C;
vector<int> v;
typedef struct {
	int c,x,y;
} muchie;
muchie M[mmax];
void swap(muchie &x,muchie &y)
 {
 muchie ax=x;
 x=y;
 y=ax;
 }
void read()
 {
 f>>n>>m;
 for(int i=1;i<=m;i++)
  f>>M[i].x>>M[i].y>>M[i].c;
 }
void qsort(int l,int r)
 {
 int dr,st,piv;
 dr=r;
 st=l;
 piv=M[(st+dr)/2].c;
 while(st<dr)
  {
  while(M[st].c<piv) st++;
  while(M[dr].c>piv) dr--;
  if(st<=dr)
   {
   swap(M[st],M[dr]);
   st++;
   dr--;
   }
  }
 if(dr>l)
  qsort(l,dr);
 if(st<r)
  qsort(st,r);
 }
void reunite(int i,int j)
 {
 i=t[i];
 j=t[j];
 for(int k=1;k<=n;k++)
  if(t[k]==i)
   t[k]=j;
 }
void solve()
 {
 qsort(1,m);
 int i,x,y,c;
 for(i=1;i<=n;i++)
  t[i]=i;
 for(i=1;i<=m;i++)
  {
  x=M[i].x;
  y=M[i].y;
  c=M[i].c;
  if(t[x]==t[y]) continue;
  reunite(x,y);
  v.push_back(x);
  v.push_back(y);
  C+=c;
  }
 }
void print()
 {
 g<<C<<endl;
 g<<((v.size()+1)/2)<<endl;
 for(unsigned i=0;i<v.size();i+=2)
  {
  g<<v[i]<<" "<<v[i+1]<<endl;
  }
 }
int main()
 {
 read();
 solve();
 print();
 return 0;
 }