#include<fstream.h>
#include<algorithm>
#include<vector>
#define MMAX 400000
#define NMAX 200000
using namespace std;
struct muchie
	{long a,b,c;};
muchie v[NMAX],sol[NMAX];
long p[NMAX];
long n,m,s,M;
bool crt(muchie x,muchie y)
{return x.c<y.c;}
void cit()
{ifstream fin("apm.in");
  fin>>n>>m;
  long i;
   for(i=1;i<=m;++i)
	   fin>>v[i].a>>v[i].b>>v[i].c;
   fin.close();
}
void solve()
{long i,j,min,max;
 sort(v+1,v+m+1,crt);
  for(i=1;i<=n;++i)
	  p[i]=i;
  for(i=1;M<=n-1;++i)
	   if(p[v[i].a]!=p[v[i].b])
		   {s+=v[i].c;
	        ++M;
			sol[M]=v[i];
	        if(p[v[i].a]>p[v[i].b])
				{min=p[v[i].b];
				 max=p[v[i].a];
				}
				 else
				{min=p[v[i].a];
				 max=p[v[i].b];
				}
			 for(j=1;j<=n;++j)
					if(p[j]==max)
						p[j]=min;
		   }
}
void afis()
{long i;
 ofstream fout("apm.out");
  fout<<s<<'\n'<<n-1<<'\n';
	  for(i=1;i<=n-1;++i)
		  fout<<sol[i].a<<" "<<sol[i].b<<'\n';
	fout.close();
}
int main()
{cit();
 solve();
 afis();
 return 0;
}